c++ - 停止 p‌r‌o‌b‌l‌e‌m 是否意味着程序无法检查其他程序？

Question

我正在上一门理论 CS 课，我们刚刚讨论了停机问题。在我的理解中，问题无法解决的原因是，如果有一个程序 Halt 告诉我们一个程序是否停止了，而你写了另一个程序 Proof 这样的

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() 的程序，该程序实质上会反转您的检查程序的输出。

Answer 1

ProofFour(program, input) 

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

在上面引用的程序中，您对 ProofFour(ProofFour,input) 的调用格式错误:第一个 Prooffour 没问题，因为它需要一个程序和一个input 作为它的输入，但是第二个 Prooffour 应该有两个参数。这意味着您需要为第二个 Prooffour 提供一对输入，如下所示:很难(如果不是不可能的话)解释为什么不可能创建 FourCheck()。

现在我稍微改变一下:

ProofFour(input)

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

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