自我指涉

说到自我指涉就不能不提说谎者悖论

我的这句话是假的  

假设这句话是真的,那么就不符合“我的这句话是假的”;假设这句话是假的,那么符合”我的这句话是假的“,则这句话是真的。

再来看一个命题

没有证据表明这个命题是真的  

假设这个命题是假的,那么有证据表明这个命题是真的;假设这个命题是真的,看似好像又出现了悖论,但是仔细想想。这个命题是真的,然而没有证据表明它是真的。存在人们不能证明其为真的真命题

哥德尔的第一不完备性定理

任意一个包含一阶谓词逻辑与初等数论的形式系统,都存在一个命题,它在这个系统中既不能被证明为真,也不能被证明为否

如果有人能够预测未来,你便可以问他我下面将伸出哪只手。如果他回答左手,你便将右手伸出;如果他回答右手,你变将左手伸出。

在计算机理论中同样有着这么一个类似的问题。

是否存在一个程序P,对于任意输入的程序w,能够判断w会在有限时间内结束或者死循环

PS 程序本身也是一种数据,因此它可以作为输入

这个问题可以被如下证明
假设停机问题有解,我们可以构造一个新的过程 U 调用 P ,并对 P 的执行结果取反(可结束则输出死循环,死循环则输出可结束),那么我们将这个 U 作为 U 过程的输入试试。显然自相矛盾。

Reference

我帮你读:「哥德尔、艾舍尔、巴赫——集异璧之大成」
停机问题