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)：第一个Prooffour是可以的，因为它需要一个程序和一个输入作为其输入，但第二个Prooffour 应该有两个参数。这意味着您需要为 second 提供一对输入Prooffour，因为：ProofFour(ProofFour,(someprog, input)) 当您使用这种定义明确的形式时，很难（如果不是不可能的话）解释为什么不可能创建 FourCheck()。

现在我稍微改变一下：

ProofFour(input)

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

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

于 2014-10-29T03:34:53.977 回答