暂停问题是否意味着程序无法检查其他程序？

Question

我正在学习理论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，输入）。如果FourCheck（）返回true，则ProofFour返回5，使FourCheck（）的输出不正确。如果FourCheck返回false，则ProofFour返回4，再次使FourCheck（）的输出不正确。

因此，假设您基本上没有程序来检查其他程序是否正确，因为您总是可以构造一个类似于Proof（）和ProofFour（）的程序，它基本上会反转您的检查程序的输出。

Answer 1

ProofFour(program, input) 

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

使用上面引用的程序，你对ProofFour(ProofFour,input)的调用是不正确的：第一个Prooffour是好的，因为它需要一个程序和一个输入作为输入，但第二个Prooffour应该有两个参数。这意味着你需要为第二个Prooffour提供一对输入，如下所示：ProofFour(ProofFour,(someprog, input))当你使用这个定义良好的形式时，很难（如果不是不可能）解释为什么不可能创建一个FourCheck（）。

现在我改变一下：

ProofFour(input)

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

这是明确定义的形式。程序中的ProofFour只是程序文本的指针。现在很明显，Fourcheck无法检查程序ProofFour。