質問: チューリングの停止性問題 チューリングの有名な停止性問題ですが、 「全てのプログラムmと全てのデータiに対して、 (1)m(i)が有限時間で停止するなら、h(m, i)は有限時間でyesを出力して停止する。 (2)m(i)が無限ループに入って停止しないなら、h(m, i)は有限時間でnoを出力して停止する。 ようなプログラムhは存在しない。」 という趣旨だと思うのですが、 人間(優秀なプログラマー)がm(i)を解読すれば、そのプログラムが有限時間で終わるか無限ループになるかは判断できるように思うのですが、この停止性問題はこの人間の判断もできないと言っているのでしょうか?それとも人間には判断できるが、それをプログラムに書いて機械に判断させることはできないといっているだけなのでしょうか?
回答: もう少し狭い世界の話として、有名な p≠np 問題というのがあります http://ja.wikipedia.org/wiki/p%e2%89%a0np%e4%ba%88%e6%83%b3 この範囲の世界の話として問題が有限時間で解けるかは重要な未解決問題ですが 現状、経験論として多分p≠np らしい、といわれています この範囲でも未解決の問題ですので、現状はなんともいえません