关于停机问题与自指性悖论

停机问题是是逻辑数学中可计算性理论的一个很经典的问题，该问题内容为：是否存在一个程序 H，对于任意输入的程序 P，能够判断 P 会在有限时间内结束或者死循环。

答案是否定的，证明如下：

假设停机问题有解，即存在一个程序能够判断程序 P 在输入 I 的情况下是否可停机 (即是否会进入死循环)。我们假设该程序为函数 H，即：

def H(P, I) -> bool:
    pass

若函数 P 在输入 I 时不会进入死循环，则 H 返回 True，否则返回 False。

然后我们定义另一个函数 U：

def U(P):
    if H(P, P):
        while True:
            pass
    else:
        return

也就是说当 H 判断 P(P) 会停机时，U 就进入死循环，否则正常返回。

那么，当 U 输入 U，也就是 U(U) 会不会停机呢？既然 H 能够判断任何程序是否会停机，那么应该也能回答这个问题，也就是：

H(U, U)

那么问题就来了，如果 H 认为 U(U) 会停机，即 H(U, U) 返回 True，那么实际上 U(U) 就会进入死循环，并不会停机。如果 H 认为 U(U) 不会停机，即 H(U, U) 返回 False，那么实际上 U(U) 就会进入死循环，并不会停机。这就推出了矛盾，也就是说 H 并不能永远给出停机问题的准确答案。

由此可以证明，不存在能够判断任意程序在特定输入下是否会在有限时间内停机的程序，停机问题无解。

与此类似的还有“理发师悖论”：一位理发师的原则是当且仅当一个人不为自己理发时他为其理发，那么这位理发师能为自己理发吗？这里“理发师悖论”实际上是罗素悖论的一个比喻，也即：对于集合 $A=\{x \mid x \notin A\}$ 判断 $A \in A$ 是否成立。

这个悖论的根本性问题为集合的自指，所以我们只要拒绝集合的自指即可解决该问题，也就是认为不存在像 $A=\{x \mid x \notin A\}$ 的集合。

同样，对于停机问题我们也可以有类似的解释，产生悖论的原因正是这个能够判断其他程序是否能停机的程序也是一个程序，那么当它判断涉及自己的程序时就可能会产生悖论，最终证明一个程序不可能判断其他所有程序是否停机。

类似的还有“全能悖论”：上帝全知全能，那么祂能创造一个自己搬不起来的石头吗？如果能，那么说明其在力量方面并非全能，如果不能，说明其在创造方面并非全能。这同样是因为自指导致的悖论，当我们将上帝的全能性作用于其本身时就会导致悖论，从而说明全能的上帝是不存在的。

此外还有一个最常见的悖论——“说谎者悖论”：“这个语句为假”是否为真。对此有许多解释，比如曾有人提出应拒绝与排中律有关的二值原理，也就是拒绝“所有语句要么为真要么为假”的主张，认为其非真非假。但是，对于另一个问题：“这个语句不为真”是否为真，也同样无法解决，类似的主张如认为其又真又假也存在无法回答的问题，即”这个语句只为假“是否为真。对此的解决比较好的有 Arthur Prior 提出的观点：语句都包含对自己真值的隐含断言，即“一加一等于二”隐含了“一加一等于二为真”的真值断言，任何一句话“A”都可以改写为“A 且这句话为真”，那么同样，“这句话为假”等价与“这句话为真且这句话为假”，而这句话本身就包含了矛盾，就像“这个东西是苹果且这个东西不是苹果”一样，所以说谎者悖论实质上是由一个一开始就含有矛盾的假语句而推导出的另一个矛盾，并不是一个悖论。不过我认为这实质上是从语言上回避了这个这个问题，是因为自然语言的不严谨导致的，并无法用来解释罗素悖论等其他涉及自指的悖论。