程序输入说明停机问题

Question

这个截屏问题的说明正确吗?

function halts(func) {
// Insert code here that returns "true" if "func" halts and "false" otherwise.
}
function deceiver() {
if(halts(deceiver))
while(true) { }
}

如果是这样，为什么有那么多的描述涉及到一个带两个参数的函数，其中一个是程序，另一个是与程序输入相同的程序?

例如:

假设我们有一个函数halt (p, W)，如果程序p在输入W时停止，那么我们写这个完全有效的Python函数:

def K(P):
if (Halts(P, P)):
while True: pass # run forever
else:
return 42 # halt!

现在，当我们调用K(K)时会发生什么?如果Halts(K,K)为True，则K(K)挂起(永远运行)如果Halts(K,K)为假，则K(K)停止所以不管怎样，Halts(K,K)都是错的。因此，halt函数不可能存在!

Answer 1

这两个输入参数只是构造矛盾证明的一个技巧，表明不存在解决停机问题的算法。

网上有很多证明的草图，例如https://www.youtube.com/watch?v=macM_MtS_w4