[工学]图灵机与计算问题

《[工学]图灵机与计算问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图灵机与计算问题(张江)··dapplehou·16位粉丝·1楼自从20世纪30年代以来，图灵机、计算这些重要的概念在科学的天空中就一直闪烁着无限的光彩。尤其是近年来量子计算机、生物计算机、DNA计算等领域的创新工作引起了世人的广泛关注。我们不禁问这样的问题，国外究竟为什么能发明出这些各式各样的计算机呢？这些意味着什么呢？其实这一切的源头都来源于计算理论。国内在介绍计算理论方面的教材虽然有不少，但一般都比较深奥难懂。所以我觉得很有必要对这些内容进行科普。于是尝试写下这么一篇文章，希望我的文章能够让你更加清楚、透彻的理解图灵机、计算等等一些基本而重要的

2、概念，并洞悉到这些概念的本质和深远涵义。本篇文章大体上可以分成四部分：首先给大家讲一讲关于图灵、哥德尔等科学家的故事；然后正式引入图灵机的概念，为了对这个概念有比较直观的理解，我采用了一个人工生命：“小虫”的比喻来叙述。接下来，文章介绍了跟图灵机有关的概念：什么是模拟，什么是“万能计算机”等等；最后是关于图灵停机问题的探讨，我个人认为很有可能未来对科学的重大突破都来源于对图灵停机问题的深入理解。在行文过程中，我除了用自己的方式介绍一些现有的基本概念之外（为了尽量表达得清楚明白，我不得不放弃理论论证的严格性），还探讨了很多我认为别人没有探讨的问题，这些

3、问题多是我自己的思考结果，而它们没有经过科学的验证。在这部分内容上我都标上了*号，希望你能有选择的看待这些问题和观点。一、故事任何科学思想、科学概念的诞生都有它的背景，在背景中往往有很多迷人的故事。关于计算理论可以追溯到1900年，当时著名的大数学家希尔伯特在世纪之交的数学家大会上给国际数学界提出了著名的23个数学问题。其中第十问题是这样的：存在不存在一种有限的、机械的步骤能够判断“丢番图方程”是否存在解？这里就提出来了有限的、机械的证明步骤的问题，用今天的话说就是算法。但在当时，人们还不知道“算法”是什么。实际上，当时数学领域中已经有很多问题都是跟

4、“算法”密切相关的，因而，科学的“算法” 定义呼之欲出。之后到了30年代的时候，终于有两个人分别提出了精确定义算法的方法，一个人是图灵，一个人是丘奇。而其中图灵提出来的图灵机模型直观形象，于是很快得到了大家的普遍接受。不知道你是否听说过图灵这个名字。可能有些人知道牛顿，知道爱因斯坦，甚至知道冯诺依曼，但不知道图灵。然而图灵的贡献绝对不亚于这些科学大师。图灵最大的贡献就是把算法这样一个基本的、深刻的概念用他的图灵机模型讲清楚了。正是因为图灵奠定的理论基础，人们才有可能发明20世纪以来甚至是人类有史以来最伟大的发明：计算机。因此人们称图灵为：计算机理论之

5、父。图灵生活的年代经历了第二次世界大战。在二战期间他曾经为英国政府效力成功破译了德国的密码，因而为英国做出了突出贡献。其实也正是因为二战，英国政府才肯掏钱让图灵制造最原始的计算机，当然这种计算机是专门用来破译密码用的，而不是我们现在用的通用计算机。（有一部片子叫《密码迷情》英文名是《enigma》就是根据图灵当时破译德国密码的故事改编的，大家有兴趣可以去找一找。）图灵这个人很古怪，只喜欢自己一个人闷头研究，不喜欢与别人交流。并且据说他还是一个同性恋者。要知道在当时的英国，同性恋行为可是大逆不道的。最后，在他事业刚刚达到顶风的时候，他自杀了。为了纪念这

6、个伟大的学者，计算机界设立了最高荣誉奖：ACM图灵奖。图灵机的产生一方面奠定了现代数字计算机的基础（要知道后来冯诺依曼就是根据图灵的设想才设计出第一台计算机的）。另一方面，根据图灵机这一基本简洁的概念，我们还可以看到可计算的极限是什么。也就是说实际上计算机的本领从原则上讲是有限制的。请注意，这里说到计算机的极限并不是说它不能吃饭、扫地等硬件方面的极限，而是仅仅就从信息处理这个角度，计算机也仍然存在着极限。这就是图灵机的停机问题。这个问题在图灵看来更加重要，在他当年的论文中，其实他是为了论证图灵停机问题才“捎带手”提出了图灵机模型的。·2006-8-2

7、116:42·回复··dapplehou·16位粉丝·2楼提到了图灵停机问题，我不禁又要提一提哥德尔定理、罗素悖论、康托尔的集合论等等一系列大事儿。早在19世纪末的时候，康托尔为集合论做了奠基性的研究。要知道，数学虽然五花八门，但是人们发现，运用集合这个概念可以概括所有的数学，也就是说集合是一切数学的基础。因而如果为集合论奠定了公理化的基础，也就等于为数学奠定了基础。康托尔就是做了这方面的贡献。另外，他为了证明实数的个数比自然数多这个结论，发明了一种被称为“对角线删除”的证明方法。没想到的是，这个方法影响非常深广，直到后来的图灵停机问题、哥德尔定理其

8、实都是该方法的不同延伸。19世纪末的人们忙于为基于集合论的数学建立公理体系大厦。然而就当这座大厦即将完工的时