チューリングマシンの限界について

質問

第２次世界大戦前、チューリングのアイデアによって数学上の
さまざまな問題を解くチューリングマシンが考え出され、
同時にチューリングマシンの限界も提示されました。
それは、数学的問題の中にはアルゴリズムに変換できない問題
は、チューリングマシンによっても解くことができない問題が
存在していることを示したそうです。
チューリングマシンをコンピュータに置き換えると、私はこれを
「解決策を、人間が論理的に置き換えることができるものは、
全てコンピュータで処理することができる」と解釈していましたが、
数学上の問題で論理的に置き換えることができない問題とは
具体的にどんな問題でしょうか？
数学にはあまり詳しくないのでよろしくお願いします。

回答No.1

rabbit_cat · ベストアンサー

チューリングマシンで解けない問題としては、「停止問題」なんかが有名です。
http://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%9E%E3%82%B7%E3%83%B3%E3%81%AE%E5%81%9C%E6%AD%A2%E5%95%8F%E9%A1%8C

お礼

ありがとうございます。
残念ながら回答いただいた内容はよく理解できないのですが、
具体例があるということがわかっただけでも納得しています。

回答No.3

Tacosan

すみません, 話をややこしくします.
「計算」を理論的に考えるうえでいろいろなモデルがあります. 有名なのは Turing機械ですが, 他にもラムダ計算だとか項書き換え系だとか D∞ とかがあります. これらはいずれも「計算可能性」について等価 (だったと思う: つまり, いずれか 1つのモデルで記述できれば他のどのモデルでも記述できる) で, 普通に「計算できる」ものは全てこれらのモデルで記述することができます. ということで, 視点を変えて「Turing機械 (など) で記述できるときに『計算できる』と呼ぼう」という考え方が提唱されました. 「Church の提唱」というやつです. これについては広く「うん, そうだね」と認知されていますが実際にそうかどうかは不明. 単に Turing機械よりも広いモデルが見付かっていないだけかも.
ということで, 一応現在では「Turing機械でアルゴリズムが記述できる」=「計算可能」とみなされています. #1, #2 の停止性判定問題 (Halting Problem) は「Turing機械では判定できない」ことが知られており, 「計算不能」とか「決定不能」とかいうラベルを貼ることになります. が, 上に書いたようなことがあるので「あらゆる意味で計算できない」かどうかはわかっていません.

回答No.2

kabaokaba

数学のところのほうが詳しい人がいそうですが・・・
チューリングマシンの停止問題そのものは
おおざっぱにやるなら
そんなに厄介な証明じゃないです．

チューリングマシン 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)は本当です

こんなふうに「自己言及」と「真偽」を絡めると
途端に厄介になるというのが本質で，
数学の再構築とか
これは結局ゲーデルの不完全性定理とかにまで発展して，
一大理論を構築することになりました
＃・・・いまでもそこから始まった話は進行中なんですよ．

>数学上の問題で論理的に置き換えることができない問題とは
これはですね，いろいろな考え方がありますが，
「一般連続体仮説」と呼ばれる問題なんかが
よくこの手の「不完全性」では引き合いにだされます．
問題そのものの説明とそれがどういう意味で
「論理の範囲外」なのかというのは，かなり数学的なので
省かせてもらいます．

お礼

ありがとうございます。
ニュアンスはだいぶわかりました。

質問の発端は、
・チューリングマシン（コンピュータ）で解けない数学の問題がある。
・論理的に表現できる解決策は、すべてコンピュータで解くことができる。
上記２つから、論理的に解決できない数学の問題っていったい何？
もしかして、証明がまだ達成されていなかったころの「四色問題」や「フェルマーの最終定理」のこと？
というのが始まりです。