图灵机与计算问题 - 御坂研究所.pdf

图灵机与计算问题 张江(email: jakezj@163.com ) 自从20 世纪30 年代以来，图灵机、计算这些重要的概念在科学的天空中就一直闪烁着 无限的光彩。尤其是近年来量子计算机、生物计算机、DNA 计算等领域的创新工作引起了 世人的广泛关注。我们不禁问这样的问题，国外究竟为什么能发明出这些各式各样的计算机 呢？这些意味着什么呢？其实这一切的源头都来源于计算理论。国内在介绍计算理论方面的 教材虽然有不少，但一般都比较深奥难懂。所以我觉得很有必要对这些内容进行科普。于是 尝试写下这么一篇文章，希望我的文章能够让你更加清楚、透彻的理解图灵机、计算等等一 些基本而重要的概念，并洞悉到这些概念的本质和深远涵义。 本篇文章大体上可以分成四部分：首先给大家讲一讲关于图灵、哥德尔等科学家的故事； 然后正式引入图灵机的概念，为了对这个概念有比较直观的理解，我采用了一个人工生命： “小虫”的比喻来叙述。接下来，文章介绍了跟图灵机有关的概念：什么是模拟，什么是“万 能计算机”等等；最后是关于图灵停机问题的探讨，我个人认为很有可能未来对科学的重大 突破都来源于对图灵停机问题的深入理解。在行文过程中，我除了用自己的方式介绍一些现 有的基本概念之外（为了尽量表达得清楚明白，我不得不放弃理论论证的严格性），还探讨 了很多我认为别人没有探讨的问题，这些问题多是我自己的思考结果，而它们没有经过科学 的验证。在这部分内容上我都标上了*号，希望你能有选择的看待这些问题和观点。 一、故事 任何科学思想、科学概念的诞生都有它的背景，在背景中往往有很多迷人的故事。关于 计算理论可以追溯到 1900 年，当时著名的大数学家希尔伯特在世纪之交的数学家大会上给 国际数学界提出了著名的23 个数学问题。其中第十问题是这样的：存在不存在一种有限的、 机械的步骤能够判断“丢番图方程”是否存在解？这里就提出来了有限的、机械的证明步骤 的问题，用今天的话说就是算法。但在当时，人们还不知道“算法”是什么。实际上，当时 数学领域中已经有很多问题都是跟“算法”密切相关的，因而，科学的 “算法”定义呼之 欲出。之后到了30 年代的时候，终于有两个人分别提出了精确定义算法的方法，一个人是 图灵，一个人是丘奇。而其中图灵提出来的图灵机模型直观形象，于是很快得到了大家的普 遍接受。 不知道你是否听说过图灵这个名字。可能有些人知道牛顿，知道爱因斯坦，甚至知道冯 诺依曼，但不知道图灵。然而图灵的贡献绝对不亚于这些科学大师。图灵最大的贡献就是把 算法这样一个基本的、深刻的概念用他的图灵机模型讲清楚了。正是因为图灵奠定的理论基 础，人们才有可能发明20 世纪以来甚至是人类有史以来最伟大的发明：计算机。因此人们 称图灵为：计算机理论之父。 图灵生活的年代经历了第二次世界大战。在二战期间他曾经为英国政府效力成功破译了 德国的密码，因而为英国做出了突出贡献。其实也正是因为二战，英国政府才肯掏钱让图灵 制造最原始的计算机，当然这种计算机是专门用来破译密码用的，而不是我们现在用的通用 计算机。（有一部片子叫《密码迷情》英文名是《enigma》就是根据图灵当时破译德国密码 的故事改编的，大家有兴趣可以去找一找。） 图灵这个人很古怪，只喜欢自己一个人闷头研究，不喜欢与别人交流。并且据说他还是 一个同性恋者。要知道在当时的英国，同性恋行为可是大逆不道的。最后，在他事业刚刚达 到顶风的时候，他自杀了。为了纪念这个伟大的学者，计算机界设立了最高荣誉奖：ACM 图灵奖。 图灵机的产生一方面奠定了现代数字计算机的基础（要知道后来冯诺依曼就是根据图灵 的设想才设计出第一台计算机的）。另一方面，根据图灵机这一基本简洁的概念，我们还可 以看到可计算的极限是什么。也就是说实际上计算机的本领从原则上讲是有限制的。请注意， 这里说到计算机的极限并不是说它不能吃饭、扫地等硬件方面的极限，而是仅仅就从信息处 理这个角度，计算机也仍然存在着极限。这就是图灵机的停机问题。这个问题在图灵看来更 加重要，在他当年的论文中，其实他是为了论证图灵停机问题才“捎带手”提出了图灵机模 型的。 提到了图灵停机问题，我不禁又要提一提哥德尔定理、罗素悖论、康托尔的集合论等 等一系列大事儿。早在 19 世纪末的时候，康托尔为集合论做了奠基性的研究。要知道，数 学虽然五花八门，但是人们发现，运用集合这个概念可以概括所有的数学，也就是说集合是 一切数学的基础。因而如果为集合论奠定了公理化的基础，也就等于为数学奠定了基础。康 托尔就是做了这方