3

私は CS の理論クラスを受講しており、停止の問題について話し合ったところです。私の理解では、問題が解決できない理由は、プログラムが停止しないかどうかを教えてくれるプログラム Halt があり、別のプログラムを書くと、

function Proof (program, input) 

if (Halt(program, input)) loop infinitely; 
else return 1

私にとって、問題の核心は、if 条件がプログラムを無限にループさせることであり、これが Halt の失敗条件であるということです。

これは私が確信していない部分です：

別のプログラムが特定の入力に対して数値 4 を返すかどうかをチェックするプログラムがあるとします。このプログラムを FourCheck としましょう。次に、次のような別のプログラム ProofFour を作成できます。

ProofFour(program, input) 

if(FourCheck(program, input) return 5; 
else return 4;

この場合、ProofFour(ProofFour,input) を呼び出すことができます。FourCheck() が true を返す場合、ProofFour は 5 を返すため、FourCheck() の出力は正しくありません。FourCheck が false を返す場合、ProofFour は 4 を返し、FourCheck() の出力が正しくなくなります。

したがって、チェッカー プログラムの出力を本質的に反転させる Proof() や ProofFour() に似たプログラムをいつでも構築できるため、他のプログラムをチェックするプログラムは本質的にないと仮定するのは正しいでしょうか。

4

1 に答える 1

-1 
ProofFour(program, input) 

if(FourCheck(program, input)) return 5; 
else return 4;

上記の引用されたプログラムでは、あなたの への呼び出し ProofFour(ProofFour,input)は形式が正しくありません: 1 つ目Prooffourは入力としてプログラムと入力を受け取るので問題ありProoffour ませんが、2 つ目は 2 つの引数を持つ必要があります。Prooffourこれは、次のように、2 番目の に対してペア入力を提供する必要があることを意味しますProofFour(ProofFour,(someprog, input)) 。

今、私はそれを少し変更します：

ProofFour(input)

if(FourCheck(ProofFour, input)) return 5; 
else return 4;

これは明確に定義されたフォームです。プログラム内の ProofFour は、プログラム テキストへの単なるポインターです。これで、Fourcheck がプログラム ProofFour をチェックできないことは明らかです。

于 2014-10-29T03:34:53.977 に答える