1701065765
前面假设了有明确程序能够判定图灵命题是否成立，这就等价于说我们能设计一个图灵机来检查死循环。
1701065766
1701065767
具体说，这个假设说的是我们能设计一个图灵机H，对于任何给定的图灵机M和输入I，都能在有限时间内判断M对输入I是会停机还是会进入死循环，停不了机。
1701065768
1701065769
设计H的问题被称为“停机问题”。注意到H本身必须总是能停机，不管答案是“是”还是“否”。因此H不能通过在I上运行M来做到这一点，因为有可能M不会停机，从而H也停不了。H必须想其他办法做到这一点。
1701065770
1701065771
虽然还不清楚H要如何做，但是我们假设了H是存在的。我们将运行H处理M和I记为H（M, I）。如果M对于I会停机就输出“是”（例如在带子上写一个1），如果M对于I不会停机就输出“否”（例如在带子上写一个0）。
1701065772
1701065773
然后图灵把H变了一下，将图灵机M也作为输入，计算H（M, M），记为H′。H′执行的步骤同H一样，它确定M处理它自身的编码M时会不会停机。不过，在得到结果后，H′执行的动作同H不一样。H在回答“是”或“否”后停机。H′则只有答案是“M对于编码M不会停机”时才会停机。如果答案是“M对于编码M会停机”，H′就进入死循环，永不停机。
1701065774
1701065775
这可能有点让人糊涂，希望你们能跟上。在计算理论的课程中，这是一个分水岭，一些学生会变得绝望，“我没法想明白这玩意！”一些学生则会拍手称快，“我喜欢这玩意！”
1701065776
1701065777
当初我也有些糊涂，不过我还是喜欢上了这些。也许你和我一样。我们来深呼吸一下，然后继续。
1701065778
1701065779
现在图灵抛出了最后的问题：
1701065780
1701065781
如果用H′自身的编码作为H′的输入，H′会怎么做呢？
1701065782
1701065783
到这个时候，拍手称快的学生也会开始头大。这确实很难想明白，不过我们还是试一试。
1701065784
1701065785
先假设H′对于输入H′不会停机。但这样就有个问题。前面说了，H′以图灵机M的编码作为输入时，如果M对于M会停机，H′就会进入死循环，反之则停机。因此，如果H′对于输入M不能停机，就意味着M对于输入M会停机。发现会有什么结果了吧？H′对于输入H′不会停机意味着H′对于输入H′会停机。但是H′不能既停机又不停机，这样就导致了矛盾。
1701065786
1701065787
因此假设H′对于H′不会停机是错误的，只能认为H′对于H′会停机。但是这样又会有问题。只有在M对于M不会停机时，H′才会停机。因此如果H′对于H′不会停机，H′对于H′就会停机。又导致了矛盾。
1701065788
1701065789
这证明H′对于输入H′既不能停机也不能不停机。这是没法做到的，因此H′不可能存在。H′本身是H的特例，因此我们就证明了H不可能存在。
1701065790
1701065791
因此不存在明确程序能解决停机问题，这就是图灵的最后结论。停机问题证明了判定问题的答案是“否”；不存在明确程序能判定任意数学命题是否为真。图灵从而彻底埋葬了希尔伯特的这个问题。
1701065792
1701065793
从上面可以看出，图灵对停机问题不可计算性的证明，与哥德尔的不完备性定理具有同样的核心思想。哥德尔提出了可以编码数学命题的方法，从而让它们可以谈论自身。图灵则提出了编码图灵机的方法，让它们可以运行自身。
1701065794
1701065795
在这里我总结一下图灵里程碑式的成就。首先，他严格定义了“明确程序”的概念。其次，他提出的图灵机为电子计算机的发明奠定了基础。第三，他改变了大多数人的观念——计算存在局限。
1701065796
1701065798
哥德尔和图灵的命运
1701065799
1701065800
19世纪时，数学和科学被认为无所不能。希尔伯特和他的追随者认为他们即将实现莱布尼茨的梦想：发现自动判定命题的方法，并证明数学无所不能。类似的，在第2章我们看到，拉普拉斯相信，根据牛顿定律，科学家原则上能预测宇宙将发生的一切。
1701065801
1701065802
然而，20世纪早期在数学和物理上的发现表明，这个无所不能实际上并不存在。量子力学和混沌摧垮了精确预测的希望，哥德尔和图灵的结果则摧垮了数学和计算无所不能的希望。然而，图灵对停机问题的解决却为另一个伟大发现——可编程电子计算机——开辟了舞台。计算机后来给科学研究以及我们的生活带来了翻天覆地的变化。
1701065803
1701065804
在20世纪30年代发表他们的成果之后，图灵和哥德尔的命运迥异。同当时许多人一样，在希特勒和第三帝国出现后，他们的命运被彻底改变了。哥德尔受到时断时续的精神问题困扰，他在维也纳一直待到1940年，最后为了不被征入德军服兵役，移民到美国。（据他的传记作者王浩说， [59] 在准备美国入籍面试时，他发现了美国宪法中的不一致性，结果他的朋友爱因斯坦在陪他去面试时只好不断同他聊天，以引开他的注意力。）
1701065805
1701065806
哥德尔和爱因斯坦一样，加入了声名卓著的普林斯顿高等研究院，并继续在数理逻辑领域做出重要贡献。然而，在20世纪60—70年代，他的精神状况不断恶化。去世前，他得了严重的妄想症，认为有人要毒害他。他拒绝进食，最终死于饥饿。
1701065807
1701065808
图灵也访问了普林斯顿高等研究院并得到了职位，但他决定回到英国。在第二次世界大战中，他加入了英国绝密的破解德军谜团密码（Enigma）的计划。以他的逻辑和统计学专长，再加上在电子计算上的成就，图灵领导研发了破译机器，最终几乎破解了所有使用谜团密码的情报。这使得英国在同德国作战时具有很大优势，并成为最终战胜纳粹的重要因素。
1701065809
1701065810
战后，图灵在曼彻斯特大学参与研制了第一批可编程电子计算机（基于通用图灵机的思想）。此后他的兴趣又回到探索大脑和身体的“计算”原理，他研究了神经学和生理学，并在发育生物学理论上做了有影响的工作，还探讨了智能计算机的可能性。然而他的生活与当时的社会道德习惯相抵触：他没有隐瞒自己的同性恋倾向。在20世纪50年代的英国同性恋是非法的，图灵因为与男性发生关系而被逮捕，并被判决接受药物“治疗”以改变他的“状况”。他也被取消了接触政府机密的权力。这些事件最终导致他在1954年自杀。有意思的是，哥德尔是因为怕被下毒而把自己饿死，图灵则是吃了有氰化物的苹果把自己毒死。图灵死的时候年仅41岁。
1701065811
1701065813
第5章 进化
1701065814
[
上一页 ]
[ :1.701065765e+09 ]
[
下一页 ]