图灵发表的论文

《论可计算数：图灵与现代计算的诞生》 克里斯·伯恩哈特图灵，

对于计算机领域是最高荣誉的代名词，但对于广大人民来说，可能会是个陌生的名字。在1936年，24岁的图灵就发表了这篇影响计算机学科构建的论文。论文的题目《论可计算数及其在判定问题上的应用 》（On Computable Numbers, with an Application to the Entscheidungsproblem），很简洁了当地体现了这篇论文的主旨，即对可计算数及其判定的研究。而这本书就围绕着这篇论文的内容，以及前前后后相关联的事情的介绍。这篇论文的主旨是为了证明一位顶尖数学家的观点是错误的，因此，图灵深入研究了计算，什么是计算，怎么定义计算，是否存在不可计算的问题，是否可以判断问题是否可计算等问题，然后通过构思出一种可以运行各种算法的机器，参考哥德尔和奥托尔给出了简洁美妙的证明。

虽然如此，但读完也只懵懵懂懂，晕晕乎乎。大体上，图灵为了证明希尔伯特作出的假设“存在一个决策程序，能够告诉我们一个论述能否通过这些公理证明（其所指的决策程序是一种清晰的计算过程，也就是我们现在所说的算法。他认为，向这个过程输入公理和可能结论，它应该告诉我们这个可能结论是否可以通过这些公理证明。）”，定义了计算，并设计出了这样的决策程序（图灵机），然后通过证明存在超出计算机解决能力的问题，来证明希尔伯特的假设的错误。通过矛盾证明法（罗素的理发师悖论），证明了停机问题（Halting Problem）和接纳问题（Acceptance Problem）都是不可判定的（存在一些图灵机可以接纳自己的编码，一些图灵机则不可以，但是不存在能够区分这两种情况的图灵机）。看了一遍，脑细胞损耗了一大半。不过，整体来说肯定比直接看论文要更容易，因为作者也提供了相关的知识背景介绍，是作为了解那篇论文的不可多得的一本书。