- ベストアンサー
チューリングマシンの限界について
第2次世界大戦前、チューリングのアイデアによって数学上の さまざまな問題を解くチューリングマシンが考え出され、 同時にチューリングマシンの限界も提示されました。 それは、数学的問題の中にはアルゴリズムに変換できない問題 は、チューリングマシンによっても解くことができない問題が 存在していることを示したそうです。 チューリングマシンをコンピュータに置き換えると、私はこれを 「解決策を、人間が論理的に置き換えることができるものは、 全てコンピュータで処理することができる」と解釈していましたが、 数学上の問題で論理的に置き換えることができない問題とは 具体的にどんな問題でしょうか? 数学にはあまり詳しくないのでよろしくお願いします。
- 3_14159
- お礼率95% (22/23)
- その他(プログラミング・開発)
- 回答数3
- ありがとう数7
- みんなの回答 (3)
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (2)
- Tacosan
- ベストアンサー率23% (3656/15482)
すみません, 話をややこしくします. 「計算」を理論的に考えるうえでいろいろなモデルがあります. 有名なのは Turing機械ですが, 他にもラムダ計算だとか項書き換え系だとか D∞ とかがあります. これらはいずれも「計算可能性」について等価 (だったと思う: つまり, いずれか 1つのモデルで記述できれば他のどのモデルでも記述できる) で, 普通に「計算できる」ものは全てこれらのモデルで記述することができます. ということで, 視点を変えて「Turing機械 (など) で記述できるときに『計算できる』と呼ぼう」という考え方が提唱されました. 「Church の提唱」というやつです. これについては広く「うん, そうだね」と認知されていますが実際にそうかどうかは不明. 単に Turing機械よりも広いモデルが見付かっていないだけかも. ということで, 一応現在では「Turing機械でアルゴリズムが記述できる」=「計算可能」とみなされています. #1, #2 の停止性判定問題 (Halting Problem) は「Turing機械では判定できない」ことが知られており, 「計算不能」とか「決定不能」とかいうラベルを貼ることになります. が, 上に書いたようなことがあるので「あらゆる意味で計算できない」かどうかはわかっていません.
- kabaokaba
- ベストアンサー率51% (724/1416)
数学のところのほうが詳しい人がいそうですが・・・ チューリングマシンの停止問題そのものは おおざっぱにやるなら そんなに厄介な証明じゃないです. チューリングマシン A が停止するかしないかを 判断できるチューリングマシン Stop があったとします. StopにAを適用した状態をStop(A)と書き, 停止と判定されたときを True, 停止しないと判定されたときを Falseとします. このとき if Stop(X) = True {無限ループ} else {何もしない} というチューリングマシン X を考えます. #自分自身の停止性に言及してるところがポイント これは,X自身が停まるか否かを Stop に判定させて ・Xが停止するときに,Xは無限ループ ・Xが停止しないときに,Xは停止する という動きをします. これは矛盾ですよね. この書き方だと,ちょっと厄介なので, これの普及版みたいのがあります. #厳密に言えばちょっと離れてるんだけども, #本質的なところは「自己言及」という点で同じですので #ご容赦を 「この紙に書いてあることは嘘です」・・・(A) と書いてある紙を考えます. (A)が本当ならば,嘘ではないので,(A)は嘘です (A)が嘘ならば,書いてあることは本当なので,(A)は本当です こんなふうに「自己言及」と「真偽」を絡めると 途端に厄介になるというのが本質で, 数学の再構築とか これは結局ゲーデルの不完全性定理とかにまで発展して, 一大理論を構築することになりました #・・・いまでもそこから始まった話は進行中なんですよ. >数学上の問題で論理的に置き換えることができない問題とは これはですね,いろいろな考え方がありますが, 「一般連続体仮説」と呼ばれる問題なんかが よくこの手の「不完全性」では引き合いにだされます. 問題そのものの説明とそれがどういう意味で 「論理の範囲外」なのかというのは,かなり数学的なので 省かせてもらいます.
お礼
ありがとうございます。 ニュアンスはだいぶわかりました。 質問の発端は、 ・チューリングマシン(コンピュータ)で解けない数学の問題がある。 ・論理的に表現できる解決策は、すべてコンピュータで解くことができる。 上記2つから、論理的に解決できない数学の問題っていったい何? もしかして、証明がまだ達成されていなかったころの「四色問題」や「フェルマーの最終定理」のこと? というのが始まりです。
関連するQ&A
- チューリング完全とは何か?
プログラムのチューリング完全性とか万能チューリング機械ってあるじゃないですか。これって、どんな挙動のプログラムでも1言語で書けるって事ですか? 色々と調べてみたのですが、どのサイトもどの資料も説明が難しかったので、ここで質問してます。私の認識は下の通りです。 チューリング完全のプログラムは、FORTRAN、C言語、Java、JavaScriptなど。 チューリング不完全のプログラムは、TeX、HTML、SQLなど。 要するに、 TeXは数式や楽譜の作成くらいの機能に制限されている。その一方で、FORTRANは数学的計算は勿論、3Gゲームや通販サイトなどFORTRAN1言語だけで何でも出来て、ありとあらゆるシステム構築に使えるって事ですか? チューリングは、戦前イギリスの数学者の名前。彼は次の命題の証明をした。どんな複雑なコンピューターシステムでも中身を分析すれば、四則演算や条件分岐や反復など数種類の小さな基本的システムパーツの組合せになっている。FORTRANやC言語はこれを全て含んでいるから、FORTANは何でも出来る。一方、SQLは惜しいがチューリング完全に必須の基本的システムパーツが数種類だけ欠けていて、限界がある。SQLオンリーでゲームを作ろうとすれば、テトリスくらいなら出来るけど、ぷよぷよを作ろうとすれば別の言語を足す事になる。 正しいですか?
- ベストアンサー
- C・C++・C#
- コンピューターシステムのXMLへの還元について
現在のコンピューターシステムはチューリングマシンなど完全な数学的記述に還元できますが、 それはあまりに人間にとっては分かりづらいものになってしまうと思います。 最終的に機械語に関連付けられているXMLを用いれば XMLのみでシステムの設計ができるようになります その方が現今の多種多様の言語を混在しているよりいいと思いませんか
- 締切済み
- XML
- チューリングマシン
チューリングマシン 現在の状態 0 0 0 0 1 1 1 読んだ文字 0 1 X □ 0 0 1 ーーーーーーーーーーーーーーーー...以下略 次の状態 1 2 0 終 1 3 1 書く文字 □ □ □ □ 0 X X 移動方向 右 右 右 右 左 右 「0」「1」が連続して書かれていて、調べたい0,1の前後は□になっています。 左から一文字ずつ消していき、その際左端が0なら1を、1なら0を1つ消す。 このチューリングマシンは、このようにして「0」「1」の数がちょうど等しいかどうかを調べるものらしいのですが、どうして次の状態に2,3がでてくるのか?また、なぜ左に戻ったりするのか?などいまいちよくわかりません。 詳しく載っているサイトか、説明をお願いします。
- 締切済み
- 数学・算数
- チューリングマシンについて
計算理論の勉強をしています。 チューリングマシンが、ある言語を「判定する」というのと「認識する」ということの違いがよくわかりません。 どなたか解説していただけないでしょうか。
- ベストアンサー
- 数学・算数
- チューリングマシンについて
Σ={0,1}の2-tape 決定性チューリングマシンの動きを、 1-tape 決定性チューリングマシンでシミュレートするにはどうすればよいか? quintuples で説明せよ。 という問題なのですが、どう解けばいいのか分かりません。 どなたか分かる方、よろしくお願いします!
- 締切済み
- 数学・算数
- プログラミングと数学的知識について
コンニチワ 有能なプログラマの経歴を見てみますと数学者などが多いですが 私はプログラミングは好きですが数学は苦手です。 公式などを使わない文章問題は比較的得意なのですが それ以外はほとんど苦手です。 プログラミングをする際必要な公式などはその都度調べています。 しかし、最近は数学的知識があってこそ生まれるアイディアというものが あるのではないかという風に考えるようになり、数学を本格的に学ぼうかと思い始めました。 やはり数学的アルゴリズムなどをきちんと勉強しておいた方が いいアイディアが生まれるのでしょうか? 専門家の方や詳しい方の意見をお聞かせください。
- 締切済み
- その他(学問・教育)
- 言語と教育についての「アルゴリズム」
言語と教育についての「アルゴリズム学習」を 学んでいます。 コンピューター用語であるというイメージが 強かったので、この分野から考えると なかなかどう考えていけばよいのか迷っています。 先生から聞いたこの「アルゴリズム学習」とは 「一定の論理的教材で有限回の解決があるとき、 その知的操作の系列を学習させることによって、問題解決能力を形成する学習方法」と言われました。 この文自体の意味が少し わかりにくいのですが、 この分野?でのアルゴリズム学習の意味について ご存知の方、教えていただけたら、うれしいです。 よろしくおねがいいたします。
- ベストアンサー
- 日本語・現代文・国語
- 万能な記述形態って何種類あるのでしょうか?
プログラマをやっています プログラミング言語を見ていくと ・アセンブラ→C言語→Javaの流れ チューリングマシンから、よく使うものを文法として括り出してきた ・Lisp ラムダ算法をプログラミング言語に落とし込んだ ・Prlog 述語論理をプログラミング言語に落としこんさ という風に、それぞれ元になっているモデルが違いますが それぞれが万能な記述形態で、どんな計算でも出来る記述携帯になっています それで疑問に思ったのですが 他にも万能な記述形態として知られている算法というのは他に何種類あるのでしょうか? 大学の初等数学までしか知らない人間レベルで分かる解説サイトなどもあれば教えて下さい
- ベストアンサー
- 数学・算数
お礼
ありがとうございます。 残念ながら回答いただいた内容はよく理解できないのですが、 具体例があるということがわかっただけでも納得しています。