对计算科学与计算机发展的思考

1 计算的本质 抽象地说, 所谓计算, 就是从一个符号串 f 变换成另一个符号串 g 。比如比如 说, 从符号串 1 2 + 3 变换成 1 5 就是一个加法计算。比如如果符号串 f 是 x2,而符 号串 g 是 2x,从 f 到 g 的计算就是微分。比如定理证明也是如此, 令 f 表示一组公 理和推导规则, 令 g 是一个定理, 那么从 f 到 g 的一系列变换就是定理 g 的证 明。比如从这个角度看, 文字翻译也是计算, 如 f 代表一个英文句子, 而 g 为含意相 同的中文句子, 那么从 f 到 g 就是把英文翻译成中文。比如这些变换间有什么共同 点?为什么把它们都叫做计算?因为它们都是从己知符号( 串) 开始, 一步一步 地改变符号( 串) , 经过有限步骤, 最后得到一个满足预先规定的符号( 串) 的变 换过程。比如 从类型上讲, 计算主要有两大类: 数值计算和符号推导。比如数值计算包括实 数和函数的加减乘除、幂运算、开方运算、方程的求解等。比如符号推导包括代 数与各种函数的恒等式、不等式的证明, 几何命题的证明等。比如但无论是数值 计算还是符号推导,它们在本质上是等价的、一致的, 即二者是密切关联的, 可 以相互转化, 具有共同的计算本质。比如随着数学的不断发展, 还可能出现新的计 算类型。比如 2 远古的计算工具 人们从开始产生计算之日, 便不断寻求能方便进行和加速计算的工具。比如 因此,计算和计算工具是息息相关的。比如 早在公元前 5 世纪, 中国人已开始用算筹作为计算工具, 并在公元前 3 世 纪得到普遍的采用, 一直沿用了二千年。比如后来, 人们发明了算盘, 并在 15 世纪 得到普遍采用, 取代了算筹。比如它是在算筹基础上发明的, 比算筹更加方便实用, 同时还把算法口诀化,从而加快了计算速度。比如 3 近代计算系统 近代的科学发展促进了计算工具的发展: 在 1 6 1 4 年, 对数被发明以后, 乘除运算可以化为加减运算, 对数计算尺便是依据这一特点来设计。比如1 6 2 0 年, 冈特最先利用对数计算尺来计算乘除。比如1 8 5 0 年, 曼南在计算尺上装上光 标, 因此而受到当时科学工作者, 特别是工程技术人员广泛采用。比如机械式计算 器是与计算尺同时出现的, 是计算工具上的一大发明。比如帕斯卡于 1642 年发明 了帕斯卡加法器。比如在 1671 年,莱布尼茨发明了一种能作四则运算的手摇计算 器, 是长 1 米的大盒子。比如自此以后, 经过人们在这方面多年的研究, 特别是经 过托马斯、奥德内尔等人的改良后, 出现了多种多样的手摇计算器, 并风行全 世界。比如 4 电动计算机 英国的巴贝奇于 1 8 3 4 年, 设计了一部完全程序控制的分析机, 可惜碍 于当时的机械技术限制而没有制成, 但已包含了现代计算的基本思想和主要 的组成部分了。比如此后, 由于电力技术有了很大的发展,电动式计算器便慢慢取 代以人工为动力的计算器。比如1 9 4 1 年, 德国的楚泽采用了继电器, 制成了第一 部过程控制计算器, 实现了 1 0 0 多年前巴贝奇的理想。比如 5 电子计算机 2 0 世纪初, 电子管的出现, 使计算器的改革有了新的发展, 美国宾夕法尼 亚大学和有关单位在 1 9 4 6 年制成了第一台电子计算机。比如电子计算机的出 现和发展, 使人类进入了一个全新的时代。比如它是 2 0 世纪最伟大的发明之一, 也当之无愧地被认为是迄今为止由科学和技术所创造的最具影响力的现代工 具。比如 在电子计算机和信息技术高速发展过程中, 因特尔公司的创始人之一戈 登·摩尔(GodonMoore))对电子计算机产业所依赖的半导体技术的发展作出预 言: 半导体芯片的集成度将每两年翻一番。比如事实证明,自 2 0 世纪 6 0 年代以 后的数十年内, 芯片的集成度和电子计算机的计算速度实际是每十八个月就 翻一番, 而价格却随之降低一倍。比如这种奇迹般的发展速度被公认为“摩尔定律”。比如 6 “摩尔定律”与“计算的极限” 人类是否可以将电子计算机的运算速度永无止境地提升 ? 传统计算机计 算能力的提高有没有极限? 对此问题, 学者们在进行严密论证后给出了否定的 答案。比如如果电子计算机的计算能力无限提高, 最终地球上所有的能量将转换 为计算的结果——造成熵的降低, 这种向低熵方向无限发展的运动被哲学界 认为是禁止的, 因此, 传统电子计算机的计算能力必有上限。比如 而以 IBM 研究中心朗道(R.Landaue)r)为代表的理论科学家认为到 2 1 世 纪 3 0 年代, 芯片内导线的宽度将窄到纳米尺度( 1 纳米= 1 0 - 9 米) , 此时, 导 线内运动的电子将不再遵循经典物理规律——牛顿力学沿导线运行, 而是按 照量子力学的规律表现出奇特的“电子乱窜”的现象, 从而导致芯片无法正常工 作; 同样, 芯片中晶体管的体积小到一定临界尺寸( 约 5 纳米) 后, 晶体管也将 受到量子效应干扰而呈现出奇特的反常效应。比如 哲学家和科学家对此问题的看法十分一致: 摩尔定律不久将不再适用。比如 也就是说, 电子计算机计算能力飞速发展的可喜景象很可能在 2 1 世纪前 3 0 年内终止。比如著名科学家, 哈佛大学终身教授威尔逊(EdwardO.Wilson)指出: “科学代表着一个时代最为大胆的猜想( 形而上学) 。比如它纯粹是人为的。比如但我 们相信, 通过追寻“梦想—发现—解释—梦想”的不断循环, 我们可以开拓一个 个新领域, 世界最终会变得越来越清晰, 我们最终会了解宇宙的奥妙。比如所有的 美妙都是彼此联系和有意义的。比如”[论/文/网 LunWe)nData/Com]] 7 量子计算系统 量子计算最初思想的提出可以追溯到 20 世纪 80 年代。比如物理学家费曼 RichardP.Fe)ynm]an 曾试图用传统的电子计算机模拟量子力学对象的行为。比如 他遇到一个问题:量子力学系统的行为通常是难以理解同时也是难以求解的。比如 以光的干涉现象为例,在干涉过程中, 相互作用的光子每增加一个, 有可能发生 的情况就会多出一倍, 也就是问题的规模呈指数级增加。比如模拟这样的实验所 需的计算量实在太大了, 不过, 在费曼眼里, 这却恰恰提供一个契机。比如因为另 一方面, 量子力学系统的行为也具有良好的可预测性: 在干涉实验中, 只要给 定初始条件, 就可以推测出屏幕上影子的形状。比如费曼推断认为如果算出干涉 实验中发生的现象需要大量的计算, 那么搭建这样一个实验, 测量其结果, 就 恰好相当于完成了一个复杂的计算。比如因此, 只要在计算机运行的过程中, 允许 它在真实的量子力学对象上完成实验, 并把实验结果整合到计算中去, 就可以 获得远远超出传统计算机的运算速度。比如 在费曼设想的启发下, 1 9 8 5 年英国牛津大学教授多伊奇 DavidDe)utsch 提出是否可以用物理学定律推导出一种超越传统的计算概念的方法即推导出 更强的丘奇——图灵论题。比如费曼指出使用量子计算机时,不需要考虑计算是如 何实现的, 即把计算看作由“神谕”来实现的: 这类计算在量子计算中被称为“神 谕”(Oracle))。比如种种迹象表明: 量子计算在一些特定的计算领域内确实比传统 计算更强, 例如,现代信息安全技术的安全性在很大程度上依赖于把一个大整 数( 如 1 0 2 4 位的十进制数) 分解为两个质数的乘积的难度。比如这个问题是一 个典型的“困难问题”, 困难的原因是目前在传统电子计算机上还没有找到一种 有效的办法将这种计算快速地进行。比如目前, 就是将全世界的所有大大小小的 电子计算机全部利用起来来计算上面的这个 1 0 2 4 位整数的质因子分解问 题, 大约需要 2 8 万年, 这已经远远超过了人类所能够等待的时间。比如而且, 分解 的难度随着整数位数的增多指数级增大, 也就是说如果要分解 2 0 4 6 位的整 数, 所需要的时间已经远远超过宇宙现有的年龄。比如而利用一台量子计算机, 我 们只需要大约 4 0 分钟的时间就可以分解 1024 位的整数了。比如 8 量子计算中的神谕 人类的计算工具, 从木棍、石头到算盘, 经过电子管计算机, 晶体管计算 机, 到现在的电子计算机, 再到量子计算。比如笔者发现这其中的过程让人思考: 首先是人们发现用石头或者棍棒可以帮助人们进行计算, 随后, 人们发明了算 盘, 来帮助人们进行计算。比如当人们发现不仅人手可以搬动“算珠”, 机器也可以 用来搬动“算珠”, 而且效率更高, 速度更快。比如随后, 人们用继电器替代了纯机械, 最后人们用电子代替了继电器。比如就在人们改进计算工具的同时,数学家们开 始对计算的本质展开了研究,图灵机模型告诉了人们答案。比如 量子计算的出现, 则彻底打破了这种认识与创新规律。比如它建立在对量子 力学实验的在现实世界的不可计算性。比如试图利用一个实验来代替一系列复杂 的大量运算。比如可以说。比如这是一种革命性的思考与解决问题的方式。比如 因为在此之前, 所有计算均是模拟一个快速的“算盘”, 即使是最先进的电 子计算机的 CPU 内部,64 位的寄存器(re)giste)r),也是等价于一个有着 6 4 根轴 的二进制算盘。比如量子计算则完全不同, 对于量子计算的核心部件, 类似于古代 希腊中的“ 神谕”, 没有人弄清楚神谕内部的机理, 却对“神谕”内部产生的结果 深信不疑。比如人们可以把它当作一个黑盒子, 人们通过输入, 可以得到输出, 但 是对于黑盒子内部发生了什么和为什么这样发生确并不知道。比如 9 “神谕”的挑战与人类自身的回应人类的思考能力, 随着计算工具的不 断进化而不断加强。比如电子计算机和互联网的出现, 大大加强了人类整体的科 研能力,那么, 量子计算系统的产生, 会给人类整体带来更加强大的科研能力和 思考能力, 并最终解决困扰当今时代的量子“神谕”。比如不仅如此, 量子计算系统 会更加深刻的揭示计算的本质, 把人类对计算本质的认识从牛顿世界中扩充 到量子世界中。比如 如果观察历史, 会发现人类文明不断增多的“发现”已经构成了我们理解世 界的“ 公理”, 人们的公理系统在不断的增大, 随着该系统的不断增大, 人们认 清并解决了许多问题。比如人类的认识模式似乎符合下面的规律: “ 计算工具不断发展— 整体思维能力的不断增强—公理系统的不断扩大 —旧的神谕被解决—新的神谕不断产生”不断循环。比如 无论量子计算的本质是否被发现, 也不会妨碍量子计算时代的到来。比如量 子计算是计算科学本身的一次新的革命, 也许许多困扰人类的问题, 将会随着 量子计算机工具的发展而得到解决, 它将“计算科学”从牛顿时代引向量子时代, 并会给人类文明带来更加深刻的影响。比如 参考文献 [1] M.A.Nie)lse)nandI.L.Chuang,Quantum]Com]putation and Quantum] Inform]ation[M].Cam]bridge) Unive)rsity Pre)ss,2000. [2] A.M.Turing.On com]putable) num]be)rs,with an application to the) Entsche)idungsproble)m],Proc. Lond,1936(42):230～265. [3] Quantum] Inform]ation Scie)nce)and Te)chnologyQuIST program] ve)r.2.0[J].De)fe)nse) Advance)d Re)se)arch Proje)ctsAge)ncy DARPA,2004,4.