图灵停机问题，引出哥德尔不完备性定理，领悟异乎寻常的逻辑哲学

一个有纸、笔、橡皮擦并且坚持行为准则的人，实质上就是一台图灵机。——图灵

图灵停机问题

通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于：是否存在一个程序P(X,Y)，对于任意的程序X，当输入Y的时候，能够判断程序X的输出是否会死循环，或者说是否停机。

结论是，不存在这样的P(X,Y)，即总有某些程序是真的，但无法提前判定。

需要明确的是，死循环并不是矛盾，矛盾是既真又假。死循环是真实存在的，也是重要的，例如一个无限循环小数1/3=0.333....；一个网页的导航链接地址还是网页本身，点击链接就会造成死循环；一个应用系统也需要一个死循环来保证系统的正常运行，如果没有死循环，那么一开机就会关机，因为系统程序已经运行结束。

康托尔对角线删除序列

图灵停机问题可以通过反证法，构建康托尔对角线删除序列来证明。

假设程序P(X,Y)存在，将每一对X和Y的组合排列在一张表格上，列表示的是输入Y，行表示的是程序X，这样P(X,Y)得到的数据，即yes或no写在第X行第Y 列的对应位置上，表示P(X,Y)判断出的，程序X作用在输入Y上是否会死循环的结果。

比如，程序X2作用在输入Y1,Y2,Y3...上，P(X,Y)给出的判断结果构成了一个序列：

no no yes yes no yes...

把表格对角线上的数据挑选出来，即第1行第1列，第2行第2列……组成了对角线序列：

yes no yes...yes...

根据这个序列可以构造一个反序列：

no yes no... no...

这个序列的每一位都与对角线序列不同，称为对角线删除序列。

试问，这个对角线删除序列是否在表格中的某一行上呢？答案是否定的。这个序列必然不在表中，因为它的第一个数据与(X1,Y1)不同，第二个数据与(X2,Y2)不同......也就是说，假设对角线删除序列在某个固定的行，比如第1314行，那么考虑第1314行，第1314列的数据，根据序列的构造方法(X1314,Y1314)对应表中的数据是与对角线删除序列上的数据不同的，因而产生了矛盾，所以这个构造出来的对角线删除序列不在表格中。

因此完全可以设计出一个程序Xn，使得输入Y1,Y2,Y3...产生的序列就是对角线删除序列，而对角线别除序列不在表中，意味着程序P(X,Y)并不能判断出程序Xn作用在任意输入上是否会死循环，或者停机。

于是不存在这样的程序P(X,Y)，能够判断所有的程序是否会死循环或停机。

哥德尔不完备性定理

世界的意义就在于事与愿离。——哥德尔

图灵停机问题揭示了哥德尔不完备性定理——任何系统都是不完备的，总存在不可判定的命题，即不能被证明亦不可被证伪。就像生活中存在的悖论，一个人不能既当演员又当观众，还有罗素的理发师悖论：只为不给自己理发的人理发，那么，理发师本人的头发谁来理？这就是理发体系的不完备。

关于定理的证明，哥德尔是通过编码将形式公理系统的原始字符一一映射成“哥德尔数”，字符按照规则构成字符串——公式，然后哥德尔构造了一个公式G，含义是哥德尔数为g的公式是不可证明的，而公式G的哥德尔数恰好为g，意味着G为真，当且仅当G为假才成立，于是就产生了悖论，因此G不能被证明亦不可被证伪。

根据哥德尔不完备性定理，可以证明很多不可解的问题。例如，欧几里得第五公理——平行公理：给定一条直线，通过此直线外的任何一点，有且只有一条直线与之平行。数学家一直尝试用前四条公理证明平行公理，然而一千多年都不可解。最终在19世纪，黎曼创立了黎曼几何——非欧几何，终于证明在欧几里得空间内平行公理既不能被证明亦不能被证伪。另外，大数学家希尔伯特提出的二十三个数学世纪难题中，第一个问题“连续统假设”——可数集基数和实数基数之间没有别的基数，也被证明是不可判定的。

图灵停机问题和哥德尔不完备性定理都是现代逻辑科学在哲学方面的重大成果，揭示了现实世界的深刻内容。不禁让人感叹，上帝是存在的，因为系统无疑是没有矛盾的，魔鬼也是存在的，因为我们不能证明没有矛盾。