#今天要来点数学吗？# #图灵机# #停机问题# #不可判定性#

图灵机是所有计算机的数学原型。

停机问题则是说，是否存在一个程序P，对任意的程序I，可以把I当作P的参数，运行P（I）来判断：若运行I，程序是否可在有限的时间里运行完毕。

很遗憾，图灵自己证明，不存在这样的P。

证明思路如下，假如有一个程序P可以判断出“所有”程序能否在有限步骤内结束，那么只需要构造一个程序P’，当P认为程序可以结束时就进入死循环，当P认为程序不能结束就终止。然后我们用P去判断P’，就得到一个图灵机版的“我在说谎”。

虽然不存在万能的P，但针对一些更加具体的算法（如自然数加法），我们有可能找到一个判定程序。

这就引出了可判定性的概念：对某类问题，若存在一个算法可在有限时间内给出“是”或“否”的答案，则称其是可判定的。

因为停机问题的答案是否定性的，所以显然存在不可判定的问题。

比如说，存在一个具有 1条纸带、2个运算符 、748 个状态的图灵机，当且仅当 ZFC 系统中存在矛盾时才会停止：http://t.cn/A69ueCtU

然而，它是否会终止运行，这个问题就是不可判定的。

所谓ZFC公理系统是指由策梅洛(Zermelo)和弗伦克尔(Fraenkel)等提出的ZF系统，在此基础上再加上选择公理所构成的ZFC公理系统。几乎相当于全部现代数学的基础。

如果假设 ZFC 是无矛盾的，则不能证明 上面的图灵机会永远运行。

背景知识：作为哥德尔不完备性定理的直接结果，有一些计算机程序，当它以无限量的内存运行时，无法通过普通数学来证明其后果。 因此，上面的程序可以简单地枚举 ZFC 公理的所有可能结果，一个接一个，直到发现矛盾时停止（例如，发现系统蕴含着命题1+1=3）。

假设 ZFC 是一致的，这个程序将永远运行下去。但是由于假设 ZFC 是一致的，则在ZFC系统里不能预言程序运行的结果，否则它将证明自身的一致性，从而违反哥德尔的第二不完备性定理！

————————————————————————

换个角度，停机问题其实也是一碗逻辑学机汤：这个世界上存在一些事，如果你不去做/执行/运作，那没有任何人或理论或方法可以提前预知其结果/后果。