计算机基本原理
图灵机与计算问题
张江(email: jakezj@163.com)
自从20世纪30年代以来,图灵机、计算这些重要的概念在科学的天空中就一直闪烁着无限的光彩。尤其是近年来量子计算机、生物计算机、DNA计算等领域的创新工作引起了世人的广泛关注。我们不禁问这样的问题,国外究竟为什么能发明出这些各式各样的计算机呢?这些意味着什么呢?其实这一切的源头都来源于计算理论。国内在介绍计算理论方面的教材虽然有不少,但一般都比较深奥难懂。所以我觉得很有必要对这些内容进行科普。于是尝试写下这么一篇文章,希望我的文章能够让你更加清楚、透彻的理解图灵机、计算等等一些基本而重要的概念,并洞悉到这些概念的本质和深远涵义。
本篇文章大体上可以分成四部分:首先给大家讲一讲关于图灵、哥德尔等科学家的故事;然后正式引入图灵机的概念,为了对这个概念有比较直观的理解,我采用了一个人工生命:“小虫”的比喻来叙述。接下来,文章介绍了跟图灵机有关的概念:什么是模拟,什么是“万能计算机”等等;最后是关于图灵停机问题的探讨,我个人认为很有可能未来对科学的重大突破都来源于对图灵停机问题的深入理解。在行文过程中,我除了用自己的方式介绍一些现有的基本概念之外(为了尽量表达得清楚明白,我不得不放弃理论论证的严格性),还探讨了很多我认为别人没有探讨的问题,这些问题多是我自己的思考结果,而它们没有经过科学的验证。在这部分内容上我都标上了*号,希望你能有选择的看待这些问题和观点。
一、故事
任何科学思想、科学概念的诞生都有它的背景,在背景中往往有很多迷人的故事。关于计算理论可以追溯到1900年,当时著名的大数学家希尔伯特在世纪之交的数学家大会上给国际数学界提出了著名的23个数学问题。其中第十问题是这样的:存在不存在一种有限的、机械的步骤能够判断“丢番图方程”是否存在解?这里就提出来了有限的、机械的证明步骤的问题,用今天的话说就是算法。但在当时,人们还不知道“算法”是什么。实际上,当时数学领域中已经有很多问题都是跟“算法”密切相关的,因而,科学的 “算法” 定义呼之欲出。之后到了30年代的时候,终于有两个人分别提出了精确定义算法的方法,一个人是图灵,一个人是丘奇。而其中图灵提出来的图灵机模型直观形象,于是很快得到了大家的普遍接受。
不知道你是否听说过图灵这个名字。可能有些人知道牛顿,知道爱因斯坦,甚至知道冯诺依曼,但不知道图灵。然而图灵的贡献绝对不亚于这些科学大师。图灵最大的贡献就是把算法这样一个基本的、深刻的概念用他的图灵机模型讲清楚了。正是因为图灵奠定的理论基础,人们才有可能发明20世纪以来甚至是人类有史以来最伟大的发明:计算机。因此人们称图灵为:计算机理论之父。
图灵生活的年代经历了第二次世界大战。在二战期间他曾经为英国政府效力成功破译了德国的密码,因而为英国做出了突出贡献。其实也正是因为二战,英国政府才肯掏钱让图灵制造最原始的计算机,当然这种计算机是专门用来破译密码用的,而不是我们现在用的通用计算机。(有一部片子叫《密码迷情》英文名是《enigma》就是根据图灵当时破译德国密码的故事改编的,大家有兴趣可以去找一找。)
图灵这个人很古怪,只喜欢自己一个人闷头研究,不喜欢与别人交流。并且据说他还是一个同性恋者。要知道在当时的英国,同性恋行为可是大逆不道的。最后,在他事业刚刚达到顶风的时候,他自杀了。为了纪念这个伟大的学者,计算机界设立了最高荣誉奖:ACM图灵奖。
图灵机与计算问题 ? ? ? ? ? ? ? ? ? ? ? 前言 一.故事 二.图灵机 三.如何理解图灵机 1.小虫的比喻 2.如何理解图灵机模型 四.计算 1.什么是计算 ...
如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 加入阅读会员!获取下载券 图灵机与计算问题 隐藏>> 图灵机与计算问题...
如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 加入会员!获取文档下载券 基于图灵机的计算问题 基于图灵机的计算问题基...
用图灵机计算热传导方程_数学_自然科学_专业资料。研究了带初值的热传导方程广义解的可计算性。首先,给出TTE的一些基本概念,然后,通过广义函数的理论得出热传导方程...
这篇论文 说,有些数学问题是不可解的。自动计算机的理论模型是在该论文中提出的,这种抽象模型 可以把推理化作一系列简单的机械动作,被称作为图灵机的模 型,有...
猜想:未来的计算机是否还需要有内、外存储器 乊分呢? ? 图灵可计算:一个问题是否可以由一个图灵机在有 限步数内完成。 ? 单个机器不两(多)台互相通信的机器...
计算理论导论(英文版)图灵机计算理论导论(英文版)图灵机隐藏>> Chapter 3 The...(随机图灵机) 写论文时从来不限制只能用低级图灵机证明问题, 可以用最先进的...
专题 第 5 卷第 12 期 2009 年 12 月 超出图灵机的互联网计算李德毅1 ...很多规律有待网络科 学进一步研究,互联网计算的不少技术与工程 设计问题也有待...
如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 从图灵机到云计算20120216 作者非本人,来自老师,仅供广大爱好者参考。作者...
之后,DNA计算不但在解决诸如NP3问题等计算 难题上做出了突出贡献,而且在构建基于分子 图灵机、分子自动机和DNA的分子逻辑门方面 * 图灵机与生命系统 1936年,图灵...
热门文档