チューリングの停止性問題

質問

チューリングの有名な停止性問題ですが、
「全てのプログラムMと全てのデータIに対して、

（１）M(I)が有限時間で停止するなら、H（M, I)は有限時間でYESを出力して停止する。
（２）M(I)が無限ループに入って停止しないなら、H(M, I)は有限時間でNOを出力して停止する。

ようなプログラムHは存在しない。」

という趣旨だと思うのですが、

人間（優秀なプログラマー）がM(I)を解読すれば、そのプログラムが有限時間で終わるか無限ループになるかは判断できるように思うのですが、この停止性問題はこの人間の判断もできないと言っているのでしょうか？それとも人間には判断できるが、それをプログラムに書いて機械に判断させることはできないといっているだけなのでしょうか？

回答No.4

BetaNona · ベストアンサー

チューリングの停止問題が主張するのはあくまで、

プログラムMとデータIの『どのような(M,I)の組み合わせが入力された場合でも』、それが停止するか否かを判定できるようなプログラムHは存在しない。

という事です。『』で括った所がポイントです。つまり、与えられたどんなプログラムについても判定出来るような万能の停止判定プログラムはない、と言ってるんですね。
「特定のM(I)について停止判定できるか」について、停止問題は何も語っていません。
例えば停止状態への遷移が一切ないプログラムは当然無限ループしますし、逆に逐次処理だけでループ構造の一切ないプログラムは停止するに決まっています。
もっと複雑なプログラムについても、プログラマーが上手く解読すれば、停止するかしないかを証明できるかもしれません。あるいは非常に複雑なプログラムであれば、どう頑張ってもできないということもあるかもしれません。また、部分的な停止問題を解くプログラム、例えばC言語ならfor(;;)やwhile(1)をヒントに無限ループを検出できるプログラムはありえます。しかし、このプログラムはforやwhileが使われていないプログラムには無力ですから、チューリングの停止判定プログラムHになる資格がないわけです。

そして、もう一つ大事なことは、そういう「プログラムが存在しない」ことを言っているだけ、ということです。
停止するかしないかを絶対に証明できないプログラムが存在する、と言ってるわけではありません。
あらゆるプログラムに対応して「そのプログラムは停止するかしないか」の証明は存在するのかもしれません。停止問題はそれを見つけ出すプログラムが存在しないと言っているだけです。証明の存在については何も言っていないのです。

これを踏まえて、質問に応えるとするなら、
＞人間（優秀なプログラマー）がM(I)を解読すれば、そのプログラムが有限時間で終わるか無限ループになるかは判断できるように思うのですが、
特定のM(I)についてなら、人間またはプログラムが停止するかどうかを判定する事はできる可能性があります（できないかもしれません。M(I)次第です）。

＞この停止性問題はこの人間の判断もできないと言っているのでしょうか？
特定のM(I)に特化した証明を人間またはプログラムが作る事は可能かもしれません（不可能かもしれません）。どんなM(I)についても適用して判定できる万能のプログラム（アルゴリズム）は存在しません。これがチューリングの主張です。

＞それとも人間には判断できるが、それをプログラムに書いて機械に判断させることはできないといっているだけなのでしょうか？
これは人間とプログラムに本質的な違いがあるかどうか、という哲学的・神学的な問題ですね。
人間の脳なんかただのニューロンオートマトンだという立場に立てば、人間と機械のできる事に違いはありません。（大多数の科学者はこっちの立場でしょう）
人間は霊感・神託（オラクル）を受け取る不思議な力があって、それはチューリングマシンの能力を超える計算を実現しているのだと信ずる立場であれば、そのときはあらゆるプログラムの停止性を判定するアルゴリズムが存在するのかもしれませんね。（そのアルゴリズムの一部には神託が組み込まれているはずです）

回答No.5

m_matsubara

もう少し狭い世界の話として、有名な　P≠NP　問題というのがあります
http://ja.wikipedia.org/wiki/P%E2%89%A0NP%E4%BA%88%E6%83%B3
この範囲の世界の話として問題が有限時間で解けるかは重要な未解決問題ですが
現状、経験論として多分P≠NP　らしい、といわれています
この範囲でも未解決の問題ですので、現状はなんともいえません

回答No.3

Tacosan

「チューリングマシンの論理体系の外部にそれとは別の新たな論理体系を作って、それでもって停止性問題を解く」っていわれても, その「別の新たな論理体系」とやらを実際に見せてもらわないことには話にならんわけですが....

1つ明らかなのは, チューリング機械の停止性判定をするためにはその「別の新たな論理体系」を完全にチューリング機械と無関係にすることは不可能ということ. つまり「別の新たな論理体系」とは言っても, それはチューリング機械を含む体系でなければならないわけです.

で, 実際「停止性判定問題が解ける」体系は容易に作れます. 単に「停止性判定問題を解くオラクル」を投入するだけです.

とはいえこの体系が判定問題に対して完全かというとそうはならず, この体系においても「解くことのできない問題」というのはやっぱり存在します.

補足

ちょっと言葉の意味が分かりません。
「オラクル」って何ですか？私はデータベースのオラクルしか知りません。

言われていることは、多分ゲーデルの不完全性定理のことを言ってられると思うのですが、

要するに、停止性問題を解決できるようにチューリングマシンの体系を拡張しても、それ以外でまた新たに解決できない問題が出てきてしまう。

そういうことですよね？

回答No.2

麻野 なぎ（@AsanoNagi）

まず、チューリングの停止性問題というのは、「……のようなプログラムは、チューリングマシンで表現（実現）できない」という意味です。

さらに、「すべてのプログラムとデータの組み合わせに対して」という前提を理解することが必要です。
「すべての M(I)」という意味は、「見たこともない」組み合わせや、「具体的には考えられない」組み合わせも含みます。
つまり、その組み合わせを「有限時間で実際に判断してみる」ということはできないわけです。
「実際に判断してみる」ということはできなくても、「そのようなプログラムは存在しない」ということが証明できたというのが、重要なのです。

回答No.1

Tacosan

この命題は,
「人間が判断できるかどうか」
については何も言っていません.

ただ, 実際には「人間の判断」とやらをどう定義するかって問題があります. 「チューリング機械で書ける」ということをもって「人間が判断できる」と定義するなら, 停止性問題から「人間も判断できない (ことがある)」という結論になる.

補足

人間が判断するということは、多分、

チューリングマシンの論理体系の外部にそれとは別の新たな論理体系を作って、それでもって停止性問題を解くということになると思うのですが、

その場合は、解ける可能性はあるということなのでしょうか？（おっしゃるように、チューリングの停止性問題はそのことには何も言っていないと思いますが）