20

私はシプサーによる計算理論入門の停止問題の証明を検討していますが、私の主な関心事は以下の証明です。

TM M がいつループしているのかわからない場合 (TM がすべての文字列に対してチューリング認識可能である理由は、受け入れることも拒否することもできないためです)、ディサイダー H は、M がループしている可能性があるかどうかをどのように判断できますか? TM D が処理を行うときも、同じ問題が発生します。

停止問題は決定不能です

4

3 に答える 3

28

これを読んで証明を視覚化しようとした後、関連する質問に対するこの回答のコードの簡略化されたバージョンであるこのコードを思いつきました。

function halts(func) {
  // Insert code here that returns "true" if "func" halts and "false" otherwise.
}

function deceiver() {
  if(halts(deceiver))
    while(true) { }
}

halts(deceiver)が返された場合は永久に実行され、 が返された場合trueは停止します。これは の定義と矛盾します。したがって、機能は不可能です。deceiverfalsedeceiverhaltshalts

于 2013-11-27T01:50:49.737 に答える
19

これは「矛盾による証明」、不条理な還元です。(ラテン語のフレーズは、理論の授業では常に有効です...もちろん、意味をなす限りです。)

このプログラムHは、あるマシンのプログラムを表す文字列と入力の 2 つの入力を持つ単なるプログラムです。証明のために、プログラム H が正しいと仮定するだけです。M がwで受け入れると、単に停止して受け入れます。それがどのように行われるかを考える必要はありません。実際、そのようなプログラムHは存在しないことを証明しようとしています...

なぜなら

そのようなプログラムが存在する場合、 Hが決定できなかった別のプログラムH'をすぐに構築できます。しかし、前提として、そのようなプログラムは存在しません。Hがすべてを決定できます。したがって、 Hを定義したように定義されたプログラムはあり得ないと結論せざるを得ません。

ところで、証明の還元法は、特にコンピューター サイエンスで使用される頻度を考えると、予想以上に議論の余地があります。ちょっと変だと思って恥ずかしがる必要はありません。魔法の用語は「非構築的」です。もしあなたが本当に野心的であると感じたら、非構築的数学に対するエレット・ビショップの批判について教授の一人に尋ねてください。

于 2011-12-06T02:16:18.627 に答える