图灵机与计算问题-Read.PDFVIP

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