[精品]计算科学与计算机发展.doc

摘要：本文通过回顾对计算工具的发展历史和人类对计算本质认识的历史，提出量子计算系统的发展和成熟 会为最终解开量子世界的“神谕”提供工具和思考方法并且提出了人类认识未知世界的规律：“计算工具 不断发展——整体思维能力的不断增强——公理系统的不断扩大 旧的神谕被解决——新的神谕不断产生”不断循环关键词：计算工具；图灵模型；量子计算；哥德尔不完备定理；神谕计算机的发展(取自百度)1引言在人类社会的早期时代，加减乘除的概念就被人们所认识到随着人类文明的发展和技术的进步，对求 方程的解，求函数的微分和积分等概念也纳入了计算的范畴伴随人类生产活动的不断增加，人们对计算的 要求也越来越大，计算丁具也再不断的改进2计算的本质在人类文明的早期，人们就认识到“加减”这些计算活动，以及它们的重要性随着，计算工具的不断 改进，人们的“计算”木身的也不断的加深了解到后来开方、求方稈的解、求微分求积分也被纳入进计算 的范畴 “什么是计算？ ”问题一直到20世纪30年，才由哥徳尔(K.Godel, 1906-1978),丘奇(A.Church, 1903-1995),图灵(A. M. TUI-ing, 1912-1954)等数学家 的工作,人们才弄清楚什么是计算的本质, 以及什么是可计算的，什么是不可计算的等根木性问题［1］。

抽象地说，所谓计算，就是从一个符号串f变换成另一个符号串g比如说，从符号串12+3变换成15 就是一个加法计算如果符号串f是x2,而符号串g是2x,从f到g的计算就是微分定理证明也是如此， 令f表示一组公理和推导规则，令g是一个定理，那么从f到g的一系列变换就是定理g的证明从这个角 度看，文字翻译也是计算，如f代表一个英文句子，而g为含意相同的中文句子，那么从f到g就是把英文 翻译成中文这些变换问有什么共同点？为什么把它们都叫做计算？因为它们都是从己知符号(串)开始，一步一步地改变符号（串），经过有限步骤，最后得到一个满足预先规定的符号（串）的变换过程从类型上讲，计算主要有两大类：数值计算和符号推导数值计算包括实数和函数的加减乘除、幕运算、 开方运算、方稈的求解等符号推导包括代数与备种函数的恒等式、不等式的证明，几何命题的证明等但 无论是数值计算还是符号推导，它们在木质上是等价的、一致的，即二者是密切关联的，可以相互转化，具 有共同的计算本质随着数学的不断发展，还可能出现新的计算类型随着计算机日益广泛而深刻的运用，计算这个原木专门的数学概念已经泛化到了人类的桀个知识领域， 并上升为一种极为普适的科学概念和哲学概念，成为人们认识事物、研究问题的一种新视角、新观念和新方 法十、“计算主义”的兴起随着计算工具的发展，一些哲学家和科学家开始从计算的视角审视世界，科学家们不仅发现大脑和生命 系统可被视作计算系统，而且发现整个批界事实上就是一个计算系统。

当康韦证明细胞自动机与图灵机等价 时，就有人开始把整个宇宙看作是计算机因为特定配置的细胞自动机原则上能模拟任何真实的过程如果 真是这样，那么，我们便可以设想一种细胞自动机，它能模拟整个宇宙实际上，我们完全可以把宇宙看作 是一个三维的细胞H动机基木粒了或其它什么层次的物质实体可以看作是这个细胞fl动机格点上的物质状 态，支配它们运动变化的规律可以看作是它们的行为规则在这些规则的作用下基木粒了发生各种变化，从 而导致宇宙的演化总之，计算或算法的观念在当今已经渗透到宇宙学、物理学、生物学乃至经济学和社会科学等诸多领域 计算已不仅成为人们认识自然、生命、思维和社会的一种普适的观念和方法，而且成为一种新的世界观一 些学者认为：生命和思维的木质是计算3远古的计算工具人们从开始产生计算ZU,便不断寻求能方便进行和加速计算的工具因此，计算和计算T具是息息相 关的早在公元前5世纪，人已开始用算筹作为计算工具，并在公元前3世纪得到普遍的采用，一直沿 用了二千年后来，人们发明了算盘（如图1所示），并在15世纪得到普遍采用，取代了算筹它是在算筹 基础上发明的，比算筹更加方便实用，同时还把算法口诀化，从而加快了计算速度。

图1古代算盘（取白百度）4近代计算系统近代的科学发展促进了计算工具的发展：在16 1 4年，对数被发明以后，乘除运算可以化为加减运算, 对数计算尺便是依据这一特点来设计1 6 2 0年，冈特最先利用对数计算尺来计算乘除18 5 0年，曼 南在计算尺上装上光标，因此而受到当时科学工作者，特别是工程技术人员广泛采用机械式计算器是与计 算尺同时出现的，是计算工具上的一大发明帕斯卡于1642年发明了帕斯卡加法器在1671年，莱布尼茨 发明了一种能作四则运算的手摇计算器（如图2, 3, 4所示），是长1米的大盒了自此以后，经过人们在这方 面多年的研究，特别是经过托马斯、奥徳内尔等人的改良后，出现了多种多样的手摇计算器，并风靡全批界图2, 3, 4手摇计算机（取自百度）5电动计算机英国的巴贝奇于1 8 3 4年，设计了一部完全稈序控制的分析机，可惜碍于当时的机械技术限制而没有 制成，但已包含了现代计算的基木思想和主要的组成部分了此后，由于电力技术有了很大的发展，电动式计 算器（如图5所示）便慢慢取代了人为动力的计算器19 4 1年，徳国的楚泽采用了继电器，制成了第一部 过程控制计算器，实现了 1 0 0多年前巴贝奇的理想。

图5电动式计算机（取自百度）6电子计算机2 0世纪初，电了管的出现，使计算器的改革有了新的发展，美国宾夕法尼亚大学和有关单位在1 9 4 6年制成了第一台电了计算机（如图6所示）电了计算机的出现和发展，使人类进入了一个全新的时代 它是2 0世纪最伟大的发明乙一，也当Z无愧地被认为是迄今为止由科学和技术所创造的最具影响力的现代工具在电了计算机和信息技术高速发展过程中，因特尔公司的创始人Z—戈登•摩尔（GodonMoore）对电了计 算机产业所依赖的半导体技术的发展作出预言：半导体芯片的集成度将每两年翻一番事实证明，自2 0 ttt 纪6 0年代以后的数I-年内，芯片的集成度和电了计算机的计算速度实际是每十八个月就翻一蒂，而价格却 随之降低一倍这种奇迹般的发展速度被公认为“摩尔定律”图6电子计算机（取自百度）7 DNA计算系统1994年11月,美国计算机科学家阿德勒曼（L. Adleman）在美国《科学》上公布DNA计算机的理论,并 成功运用DNA计算机解决了一个有向哈密顿路径问题［7］DNA计算机的提出，产生于这样一个发现，即生 物与数学的相似性：（1）生物体异常复杂的结构是对由DNA序列表示的初始信息执行简单操作（复制、剪接） 的结果；（2）可计算函数f（3）的结果可以通过在3上执行一系列基木的简单函数而获得。

阿徳勒曼不仅意识到这两个过程的相似性，而且意识到可以利用生物过程来模拟数学过程更确切地说 是，DNA串可用于表示信息，酶可用于模拟简单的计算这是因为：首先，DNA是由称作核昔酸的一些单元组 成，这些核昔酸随着附在其上的化学组或基的不同而不同共有四种基：腺嚓吟、鸟嚓吟、胞卩密I症和胸腺“密 旋，分别用A、G、C、T表示单链DNA可以看作是由符号A、G、C、T组成的字符串从数学上讲，这意味 着可以用一个含有四个字符的字符集刀二A、G、C、T来为信息编码（电子计算机仅使用0和1这两个数字） 其次，DNA序列上的一些简单操作需要酶的协助，不同的酶发挥不同的作用起作用的有四种酶：限制性内 切酶，主要功能是切开包含限制性位点的双链DNA； DNA连接酶，它主要是把一个DNA链的端点同另一个链连 接在一起；DNA聚合酶，它的功能包括DNA的复制与促进DNA的合成；外切酶，它可以有选择地破坏双链或 单链DNA分子正是基于这四种酶的协作实现了 DNA计算DNA计算与电了计算机完全不同，它的计算单元是装在试管培养液中的DNA长链通过控制试管的温度 和向试管中投放反应物，来进行计算8量子计算系统量了计算最初思想的提出可以追溯到20世纪80年代。

物理学家费曼RichardP. Feynman曾试图用传统 的电了计算机模拟量了力学对彖的行为他遇到一个问题:量了力学系统的行为通常是难以理解同时也是难以 求解的以光的干涉现象为例，在干涉过稈中，相互作用的光了每增加一个，有可能发生的情况就会多出一 倍，也就是问题的规模呈指数级增加模拟这样的实验所需的计算童实在太大了，不过，在费曼眼里，这却 恰恰提供一个契机因为另一方面，量了力学系统的行为也具有良好的可预测性：在干涉实验中，只要给定 初始条件，就可以推测出屏幕上影了的形状费曼推断认为如果算出干涉实验中发生的现彖需要大量的计算, 那么搭建这样一个实验，测量其结果，就恰好相当于完成了一个复杂的计算因此，只要在计算机运行的过 程中，允许它在真实的量了力学对彖上完成实验，并把实验结果整合到计算中去，就可以获得远远超出传统 计算机的运算速度［8］在费曼设想的启发下，19 8 5年英国牛津大学教授多伊奇DavidDeutsch提出是否可以用物理学定律 推导出一种超越传统的计算概念的方法即推导出更强的丘奇——图灵论题费曼指出使用量了计算机时，不需 要考虑计算是如何实现的，即把计算看作由“神谕”来实现的：这类计算在量子计算中被称为“神谕” (Ora cle)。

种种迹象表明：量了计算在一些特定的计算领域内确实比传统计算更强，例如，现代信息安全技术的安 全性在很大程度上依赖于把一个大整数(如1 0 2 4位的I-进制数)分解为两个质数的乘积的难度这个问 题是一个典型的“困难问题”，困难的原因是目前在传统电了计算机上还没有找到一种有效的办法将这种计 算快速地进行目前，就是将全世界的所有大大小小的电了计算机全部利用起来来计算上面的这个1 0 2 4 位整数的质因了分解问题，大约需要2 8 )1年，这已经远远超过了人类所能够等待的时间而且，分解的难 度随着整数位数的增多指数级增大，也就是说如果要分解2 0 4 6位的整数，所需要的时间已经远远超过宇 宙现有的年龄而利用一台量了计算机，我们只需要大约4 0分钟的时间就可以分解1024位的整数了 ［9］9量子计算中的神谕人类的计算工具，从木棍、石头到算盘，经过电了管计算机，晶体管计算机，到现在的电了计算机，再 到量了计算笔者发现这其中的过程让人思考：首先是人们发现用石头或者棍棒可以帮助人们进行计算，随 示，人们发明了算盘，来帮助人们进行计算当人们发现不仅人手可以搬动“算珠”，机器也可以用来搬动 “算珠”，而且效率更高，速度更快。

随后，人们用继电器替代了纯机械，最后人们用电了代替了继电器 就在人们改进计算工具的同时，数学家们开始对计算的木质展开了研究，图灵机模型告诉了人们答案量了计算的出现，贝慚底打破了这种认识与创新规律它建立在对量了力学实验的在现实批界的不可计 算性试图利用一个实验来代替一系列复杂的大量运算这是一种革命性的思考与解决问题的方式［1 0］因为在此Z前，所有计算均是模拟一个快速的“算盘”，即使是最先进的电了计算机的CPU内部,64位 的寄存器(register),也是等价于一个有着6 4根轴的二进制算盘量了计算则完全不同，对于最了计算的 核心部件，类似于古代希腊中的“神谕”，没有人弄清楚神谕内部的机理，却对“神谕”内部产生的结果深 信不疑［11］人们可以把它当作一个黑盒了，人们通过输入，可以得到输出，但定对于黑盒了内部发生了什 么和为什么这样发生确并不知道10 “神谕”的本质与哥德尔不完备性量子计算在信息的承载体上与经典计算毫无区别:它同样利用二进制比特——称为量了比特——来进行 运算但是，量了力学的一个I-分“反肓觉”的奇特现象铸就了量了比特。