年中在读《量子计算与量子信息原理》的时候，写了一篇《图灵停机问题的一个简单论述》的阅读笔记，对大学时没学明白的图灵停机问题有了一些基本认识。今天在读《复杂》的时候，里面采用了另外一种等价的说法，在符号形式上看起来略有差异，如今记录一下加深印象。
回顾量子一书中的描述，先假设存在算法A具有判定任意算法是否能够停止运算的能力，用符号表述也就是
对于算法T输入mh，可以停止运算时，A回答是
A(T(mh))=是
对于算法T输入mf，不能停止运算时，A回答否
A(T(mf))=否
现在构造算法B，对于A输出为是的，B算法不能停止运算
B(A(T(mh))=不
对于A输出为否的，B算法可以停止运算
B(A(T(mf))=停
此时，如果将算法B作为算法A和算法B的输入就会推出矛盾
根据A算法具备的能力，那么以下的两个代入应该成立
A(B(A(T(mh)))=否
A(B(A(T(mf)))=是
根据B算法具备的能力，那么以下的代入应该成立
B(A(B(A(T(mh))))=停
B(A(B(A(T(mf))))=不
矛盾出现了，对于输入mh，既能停止运算，又不能停止运算；对于输入mf，既不能停止运算，有能停止运算。所以B不存在，A也不存在。
复杂一书中的描述如下
H算法（图灵机）可以判定任意M算法对于任意输入I的停机行为，即
对于M(I)可以停止，H(M, I)=是
对于M(I)不可停止，H(M, I)=否
如果将M算法作为M的输入，那么根据前面的假设H也能够得到是与否的结论。不过，这时，我们去构造一个算法H’，对于M(M)可以停止的时候，H’算法不可停止；相反则课停止，即
对于M(M)可以停止，H'(M,M)=不
对于M(M)不可停止，H'(M,M)=停
这时问H'(H’,H’)会如何呢？ 根据H’构造的逻辑，H'(H’)如果可以停止，那么H'(H’,H’)不能停止，而如果它不能停止，又是可停止的，于是得到矛盾。
这两种叙述看起来有许多不同，但本质的两个方面是相同的。其一，算法本身可以作为算法的输入，这点观察不是显而易见的，并且也不那么容易理解。这点观察有个简单的等价问题就是理发师问题，此外，还有就是罗素的集合悖论以及哥德尔证明数学完备性的基础。拓展到计算机中，所有学过计算机软件理论的人都感到学习编译原理的难度要高过操作系统、计算机网络等，主要原因大概就是因为编译过程的输入、处理规则和输出都是程序，非常反直觉。其二，无矛盾是理性推理的基石，这点学过一些基础数学证明的人都曾会有些体会。
