哈林问题的这个说明是否正确?
function halts(func) {
// Insert code here that returns "true" if "func" halts and "false" otherwise.
}
function deceiver() {
if(halts(deceiver))
while(true) { }
}
如果是这样,为什么这么多描述涉及一个带有两个参数的函数,其中一个是程序,另一个是与程序输入相同的程序?
例如:
假设我们有一个函数 Halts(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) 为 False,则 K(K) 停止 所以无论哪种方式,Halts(K,K) 都是错误的。因此,Halts 函数不存在!