停止問題是否意味着程序無法檢查其他程序？

我正在參加理論課，我們剛剛討論了暫停問題。在我的理解，這個問題不能得到解決的原因是，如果有一個程序暫停，告訴我們沒有一個程序是否會停機，而你寫另一個程序證明這樣停止問題是否意味着程序無法檢查其他程序？

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，輸入）。如果FourCheck（）返回true，那麼ProofFour返回5，使FourCheck（）的輸出不正確。如果FourCheck返回false，則ProofFour返回4，再次使FourCheck（）的輸出不正確。

因此，假設您基本上沒有程序來檢查其他程序是否正確，因爲您總是可以構建一個類似於Proof（）和ProofFour（）的程序，它基本上反轉了檢查程序的輸出。

來源

2014-10-29 Darvish Kamalia

我想你回答了你自己的問題。 – ThomasMcLeod 2014-10-29 01:44:23

總是可以「倒置」程序的輸出嗎？ – 2014-10-29 01:49:43

這個問題似乎是無關緊要的，因爲應該在http://cstheory.stackexchange.com/ – kay 2014-10-29 01:56:01

-1

ProofFour(program, input) 

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

通過以上引述的程序，是形成不良的，以ProofFour(ProofFour,input)來電：第一Prooffour是確定的，因爲它需要一個程序，並輸入作爲其輸入，但第二Prooffour應該有兩個參數。這意味着您需要爲第二個Prooffour提供一對輸入，如下所示：當您使用這個定義明確的表單時，很難解釋爲什麼無法創建FourCheck（）。

現在我改變一點點：

ProofFour(input) 

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

這是明確的形式。程序中的ProofFour只是一個指向程序文本的指針。現在很明顯，Fourcheck無法檢查ProofFour程序。

來源

2014-10-29 03:34:53

你可以做類似於暫停問題。 – 2014-10-29 03:35:30

停止問題是否意味着程序無法檢查其他程序？

回答

相關問題