1

哈林问题的这个说明是否正确?

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 函数不存在!

4

1 回答 1

0

这两个输入参数只是构造矛盾证明的一个技巧,表明不存在用于停止问题的算法。

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

于 2021-08-29T16:54:44.847 回答