0

停止問題は、入力とプログラムが与えられた場合、プログラムが停止するかどうかを判断できるアルゴリズムがないことを示しています。これにより、この問題は決定不能になります。停止の問題に関する私の誤解は、プログラムに無限ループがあるかどうかをチェックできる別のプログラムを作成できないかということです。ループが停止しないケースをチェックして、それに基づいてプログラムが停止するかどうかを判断できる可能性があることを意味します。この問題に対する私の理解のどこが間違っているのか教えてください。

4

1 に答える 1

0

ええと、停止問題の証明は非常に簡単です。特定のプログラムが停止するかどうかを通知するプログラムがあると仮定しましょう (簡単にするために、入力については忘れてください)。このプログラムを doesHalt(program) としましょう。という名前の新しいプログラムを書きましょう。

myHalt() 
  if doesHalt(myHalt):
     infinite loop
  else 
     return

の戻り値は何ですか

doesHalt(myHalt)

特定の質問に答えるには: ループを調べるプログラムは、特定のループが停止しているかどうかをどのように認識しますか? ループしますか

for (i = 1; i += 10; ) {
   if (i == 7) break;
}

永遠にループするかどうか？あなたのプログラムはどのようにそれを理解しましたか?

于 2015-11-13T04:09:57.380 に答える