停机问题

假设停机问题有解，即：存在过程H(P, I)可以判断对于程序P在输入I的情况下是否可停机。假设P在输入I时可停机，H输出“停机”，反之输出“死循环”，即可导出矛盾：

显然，程序本身也是一种数据，因此它可以作为输入（例如Pascal的编译器本身就可以用Pascal所写成，所以程序在自己身上运行自己也是合理的），故H应该可以判定当将P作为P的输入时，P是否会停机。然后我们定义一个过程U(P)，其流程如下：

U(P)调用H(P, P)：

如果H(P, P)进入死循环，U(P)就停机。

如果H(P, P)停机，U(P)就进入死循环。

也就是说，U(P)做的事情就是做出与H(P, P)的输出相反的动作。

伪代码及其注释表示如下：

上面把H(P, P)包装在U(P)内，也就是用U()来模拟H()。H()的输出可能出现两种状况：

假设H(U, U)输出停机 -> U(U)进入死循环：由定义知二者矛盾（与过程H的定义相矛盾，因为照H自己本来的定义，H(U, U)的结果应该和U(U)相同，但U()的定义却是永远输出与H()相反的结果。）

假设H(U, U)输出死循环 -> U(U)停机：两者一样矛盾。

因此，H不是总能给出正确答案，故前述的假设不成立，不存在解决停机问题的方法。

理发师悖论：村子里有个理发师，这个理发师有条原则是，对于村子里所有人，当且仅当这个人不自己刮胡子，理发师就给这个人刮胡子。如果这个人自己刮胡子，理发师就不给这个人刮胡子。无法回答的问题是，理发师给自己刮胡子么？

停机测试悖论：计算机里面有个测试程序，这个测试程序的原则是，对于计算机里所有程序，当且仅当这个程序不递归调用自己（输出停机），测试程序就调用它（对应不停机）。如果这个程序递归调用自己（对应不停机），测试程序就不调用它（对应停机）。无法回答的问题是，测试程序递归调用自己么？