停机问题

证明

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

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

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

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

intH(procedure,Input);// 这里的H函数有两种返回值，死循环(1) 或 停机(0)intU(P){if(H(P,P)==1){// 如果H死循环return0;// 此时会停机}else{// 否則while(1){}// 此时会死循环}}

上面把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不是总能给出正确答案，故前述的假设不成立，不存在解决停机问题的方法。

相似的悖论

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

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

参见

理发师悖论

哥德尔不完备定理

未解决的数学问题

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。