查看: 4497|回复: 0

[转帖]理解计算

字体大小: 正常放大

xiaogao

20 主题	1 听众	208 积分

该用户从未签到

电梯直达

1^#

发表于 2005-4-30 23:09 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

信人: CleverWang(小鱼儿), 信区: CFD 标题: 理解计算发信站: 瀚海星云 (2004年10月14日10:21:11 星期四), 站内信件 http://combinatorics.net.cn/readings/lijie.htm 摘自《科学》2003年7月（55卷4期）理解计算郝宁湘随着计算机日益广泛而深刻的运用，计算这个原本专门的数学概念已经泛化到了人类的整个知识领域，并上升为一种极为普适的科学概念和哲学概念，成为人们认识事物、研究问题的一种新视角、新观念和新方法。什么是计算与计算的类型在大众的意识里，计算首先指的就是数的加减乘除，其次则为方程的求解、函数的微分积分等；懂的多一点的人知道，计算在本质上还包括定理的证明推导。可以说，“计算”是一个无人不知元人不晓的数学概念，但是，真正能够回答计算的本质是什么的人恐怕不多。事实上，直到1930年代，由于哥德尔（K.Godel ，1906- 1978）、丘奇（A.Church，1903-1995 ）、图灵（A.M.TUI-ing ，1912-1954 ）等数学家的工作，人们才弄清楚什么是计算的本质，以及什么是可计算的、什么是不可计算的等根本性问题。抽象地说，所谓计算，就是从一个符号串f 变换成另一个符号串g.比如说，从符号串12+3变换成15就是一个加法计算。如果符号串f 是，而符号串g 是2x，从f 到g 的计算就是微分。定理证明也是如此，令f 表示一组公理和推导规则，令g 是一个定理，那么从f 到g 的一系列变换就是定理g 的证明。从这个角度看，文字翻译也是计算，如f 代表一个英文句子，而g 为含意相同的中文句子，那么从f 到g 就是把英文翻译成中文。这些变换间有什么共同点？为什么把它们都叫做计算？因为它们都是从己知符号（串）开始，一步一步地改变符号（串），经过有限步骤，最后得到一个满足预先规定的符号（串）的变换过程。从类型上讲，计算主要有两大类：数值计算和符号推导。数值计算包括实数和函数的加减乘除、幕运算、开方运算、方程的求解等。符号推导包括代数与各种函数的恒等式、不等式的证明，几何命题的证明等。但无论是数值计算还是符号推导，它们在本质上是等价的、一致的，即二者是密切关联的，可以相互转化，具有共同的计算本质。随着数学的不断发展，还可能出现新的计算类型。计算的实质与E 奇－图灵论点为了回答究竟什么是计算、什么是可计算性等问题，人们采取的是建立计算模型的方法。从20世纪30年代到40年代，数理逻辑学家相继提出了四种模型，它们是一般递归函数、λ可计算函数、图灵机和波斯特（E.L.Post，1897-1954 ）系统。这种种模型完全从不同的角度探究计算过程或证明过程，表面上看区别很大，但事实上却是等价的，即它们完全具有一样的计算能力D 在这一事实基础上，最终形成了如今著名的丘奇- 图灵论点：凡是可计算的函数都是一般递归函数（或是图灵机可计算函数等）。这就确立了计算与可计算性的数学含义。下面主要对一般递归函数作一简要介绍。哥德尔首先在1931年提出了原始递归函数的概念。所谓原始递归函数，就是由初始函数出发，经过有限次的使用代人与原始递归式而做出的函数。这里所说的初始函数是指下列三种函数：（1 ）零函数0 （x ）=0（函数值恒为零）；（2 ）射影函数（x1，x2，…， xn）=xi （1 ≤i ≤n ）（函数的值与第i 个自变元的值相同）；后继函数S （x ） =x+1（其值为x 的直接后继数）。代人与原始递归式是构造新函数的算子。代人（又名叠置、迭置），它是最简单又最重要的算子，其一般形式是：由一个m 元函数f 与m 个n 元函数g1，g2，…，gm造成新函数f （g1（x1，x2，…，xn）， g2（x1，x2，…，xn），…，gm（x1，x2，…，xn））。原始递归式，其一般形式为特殊地为其特点是，不能由g ，h 两已知函数直接计算新函数的一般值f （u ，x ），而只能依次计算f （u ，0 ），f （u ，1 ），f （u ，2 ），…；但只要依次计算，必能把任何一个f （u ，x ），对值都算出来。换句话说，只要g ，h 有定义且可计算，则新函数f 也有定义且可计算。根据埃尔布朗（J.Herbrand，1908-1931 ）一封信的暗示，哥德尔于1934年引进了一般递归函数的概念。后经克林（S.C.Kleene，1909-1994 ）的改进与阐明，便出现了现在普遍采用的定义。所谓一般递归函数，就是由初始函数出发，经过有限次使用代人、原始递归式和μ算子而做成的有定义的函数。这里的μ算子就是造逆函数的算子或求根算子。如此定义的一般递归函数比原始递归函数更广，这是没有任何疑问的。但是，人们还是可以问：这样定义的函数是否已经包括了所有直观上的可计算函数？如果还有更广的可计算函数又该怎样定义？在受到这类问题困惑的同时，丘奇、克林又提出了一类可计算函数，叫做λ可计算函数。但事隔不久，丘奇和克林便分别证明了λ可计算函数正好就是一般递归函数，即这两类可计算函数是等价的、一致的。在这一有力的证据基础上，丘奇于1936年公开发表了他早在两年前就孕育过的一个论点，即著名的丘奇论点：每个能行地可计算的函数都是一般递归函数。与此同时，图灵定义了另一类可计算函数，叫做图灵机可计算性函数，并且提出了著名的图灵论点：能行可计算函数都是用图灵机可计算的函数。图灵机是图灵提出的一种计算模型，或一台理论计算机口它可以说是对人类计算与机器计算的最一般、最高度的抽象。一年后，图灵进一步证明了图灵机可计算函数与λ可定义函数是一致的，当然也就和一般递归函数一致、等价。于是，表面上不同的三类可计算函数在本质上就是一类。这样一来，丘奇论点和图灵论点也就是一回事了，现将它们合称为丘奇- 图灵论点，即直观的能行可计算函数等同于一般递归函数、可λ 定义函数和图灵机可计算函数。丘奇－图灵论点的提出，标志着人类对可计算函数与计算本质的认识达到了空前的高度，它是数学史上一块夺目的里程碑。一般递归函数比较抽象，为此给出一种较为直观的解释。大家知道，凡能够计算的，即使是“心算”，总可以把其计算过程记录下来，而且是逐个步骤逐个步骤地记录下来。所谓计算过程，是指从初始符号或已知符号开始，一步一步地改变（变换）符号，最后得到一个满足预先规定的条件的符号，并从该符号按照一定方法得到所求结果，即所求函数的值的全过程。可如此计算的函数，一般称为可以在有限步骤内计算的函数。现已证明：凡是可以从某些初始符号开始，而在有限步骤内计算的函数都是递归函数。由此可以看到，“能够记录下来”便符合了可计算性或递归性的本质要求。一般递归函数的实质也由此显得十分直观易懂。丘奇－图灵论点的提出与确认，在数学和计算机科学上具有重大的理论和现实意义。正如我国数理逻辑专家莫绍揆教授所言，有了这个论点以后，就可以断定某些问题是不能能行地解决或不能能行地判定的。对于计算机科学，丘奇- 图灵论点的意义在于它明确刻画了计算机的本质或计算机的计算能力，确定了计算机只能计算一般递归函数，对于一般递归函数之外的函数，计算机是无法计算的。 DNA 计算：新型计算方式的出现 1994年11月，美国计算机科学家阿德勒曼（L.Adleman ）在美国《科学》上公布DNA 计算机的理论，并成功运用DNA 计算机解决了一个有向哈密顿路径问题。 DNA 计算机的提出，产生于这样一个发现，即生物与数学的相似性：（1 ）生物体异常复杂的结构是对由DNA 序列表示的初始信息执行简单操作（复制、剪接）的结果；（2 ）可计算函数f （ω）的结果可以通过在ω上执行一系列基本的简单函数而获得。阿德勒曼不仅意识到这两个过程的相似性，而且意识到可以利用生物过程来模拟数学过程。更确切地说是，DNA 串可用于表示信息，酶可用于模拟简单的计算。这是因为：首先，DNA 是由称作核昔酸的一些单元组成，这些核昔酸随着附在其上的化学组或基的不同而不同。共有四种基：腺嘌呤、鸟嘌呤、胞嘧啶和胸腺嘧啶，分别用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 计算机还没有一个固定的程式。由于问题的多样性，导致所采用的分子生物学技术的多样性，具体问题需要设计具体的实验方案口这便引出了两个根本性问题（也是阿德勒曼最早意识到的）：（1 ）DNA 计算机可以解决哪些问题确切地说，DNA 计算机是完备的吗？即通过操纵DNA 能完成所有的（图灵机）可计算函数吗？（2 ）是否可设计出可编程序的DNA 计算机？即是否存在类似于电子计算机的通用计算模型——图灵机——那样的通用DNA 系统（模型）？目前，人们正处在对这两个根本性问题的研究过程之中口在笔者看来，这就类似于在电子计算机诞生之前的20世纪三四十年代理论计算机的研究阶段。如今，已经提出了多种DNA 计算模型，但各有千秋，公认的DNA 计算机的“图灵机”还没有诞生。相对而言，一种被称为“剪接系统”的DNA 计算机模型较为成功。有了“剪接系统”这个DNA 计算机的数学模型后，便可以来回答前面提出的DNA 计算的完备性与通用性问题。前面讲过，丘奇- 图灵论点深刻地刻画了任何实际计算机的计算能力——任何可计算函数都是可由图灵机计算的函数（一般递归函数）。现已证明：剪接系统是计算完备的，即任何可计算函数都可用剪接系统来计算 D 反之亦然。这就回答了DNA 计算机可以解决哪些问题——全部图灵机可计算问题。至于是否存在基于剪接的可编程计算机，也有了肯定的答案：对每个给定的字符集 T ，都存在一个剪接系统，其公理集和规则集都是有限的，而且对于以T 为终结字符集的一类系统是通用的。这就是说，理论上存在一个基于剪接操作的通用可编程的DNA 计算机。这些计算机使用的生物操作只有合成、剪接（切割- 连接）和抽取。 DNA 计算机理论的出现意味着计算方式的重大变革。当然，引起计算方式重大变革的远不止DNA 计算机，光学计算机、量子计算机、蛋白质计算机等新型计算机模型层出不穷，它们使原有的计算方式发生了前所未有的变化。计算方式及其演变简单地讲，所谓计算方式就是符号变换的操作方式，尤其指最基本的动作方式。广义地讲，还应包括符号的载体或符号的外在表现形式，亦即信息的表征或表达。比如，中国古代的筹算，就是用一组竹棍表征的计算方式，后来的珠算则是用算盘或算珠表征的计算方式，再后来的笔算又是一种用文字符号表征的计算方式，这一系列计算方式的变化，表现出计算方式的多样性与不断进化的趋势。相对于后来出现的机器计算方式，上述各种计算方式均可归结为“手工计算方式”，其特点是用手工操作符号，实施符号的变换。不过，真正具有革命性的计算方式，还是随着电子计算机的产生才出现的。机器计算的历史可以追溯到1641年，当年18岁的法国数学家帕斯卡从机械时钟得到启示：齿轮也能计数，于是成功地制作了一台齿轮传动的八位加法计算机口这使人类计算方式、计算技术进入了一个新的阶段。后来经过人们数百年的艰辛努力，终于在1945年成功研制出了世界上第一台电子计算机。从此，人类进入了一个全新的计算技术时代。从最早的帕斯卡齿轮机到今天最先进的电子计算机，计算机已经历了四大发展时期。计算技术有了长足的发展。这时计算表现为一种物理性质的机械的操作过程。符号不再是用竹棍、算珠、字母表征，而是用齿轮表征，用电流表征，用电压表征等等。但是，无论是手工计算还是机器计算，其计算方式——操作的基本动作都是一种物理性质的符号变换（具体是由“加”“减”这种基本动作构成）。二者的区别在于：前者是手工的，运算速度比较慢；后者则是自动的，运算速度极快。如今出现的DNA 计算无疑有着更大的本质性变化，计算不再是一种物理性质的符号变换，而是一种化学性质的符号变换，即不再是物理性质的“加”“减”操作，而是化学性质的切割和粘贴、插人和删除。这种计算方式将彻底改变计算机硬件的性质，改变计算机基本的运作方式，其意义将是极为深远的。阿德勒曼在提出DNA 计算机的时候就相信，DNA 计算机所蕴涵的理念可使计算的方式产生进化。量子计算机在理论上的出现，使计算方式的进化又有了新的可能。电子计算机的理论模型是经典的通用图灵机——一种确定型图灵机，量子计算机的理论模型— —量子图灵机则是一种概率型图灵机。直观一些说，传统电脑是通过硅芯片上微型晶体管电位的“开”和“关”状态来表达二进位制的0 和1 ，从而进行信息数据的处理和储存。每个电位只能处理一个数据，非0 即1 ，许多个电位依次串连起来，才能共同完成一次复杂的运算。这种线性计算方式遵循普通的物理学原则，具有明显的局限性。而量子计算机的运算方式则建立在原子运动的层面上，突破了分子物理的界限。根据量子论原理，原子具有在同一时刻处于两个不同位置、又同时向上下两个相反方向旋转的特性，称为“量子超态”。而一旦有外力干扰，模糊运动的原子又可以马上归于准确的定位。这种似是而非的混沌状态与人们熟知的常规世界相矛盾，但如果利用其表达信息，却能发挥出其瞬息之间千变万化而又万变不离其宗的神奇功效。因为当许多个量子状态的原子纠缠在一起时，它们又因量子位的 “叠加性”，可以同时一起展开“并行计算”，从而使其具备超高速的运算能力。电子线性计算方式如同万只蜗牛排队过独木桥，而量子并行运算好比万只飞鸟同时升上天空。计算方式演变的意义计算方式的不断进化有着十分重要的理论意义和现实意义，笔者认为至少表明以下两方面。其一，计算方式是一种历史的结果，而非计算本性的逻辑必然。加拿大的卡里（L.Kari）指出：“DNA 计算是考察计算问题的一种全新方式。或许这正是大自然做数学的方法：不是用加和减，而是用切割和粘贴、用插入和删除。正如用十进制计数是因为我们有十个手指那样，或许我们目前计算中的基本功能仅因为人类历史使然。正如人们已经采用其他进制计数一样，或许现在是考虑其他的计算方式的时候了。”笔者以为，这一说法是很有启示性的。确实，仔细回顾一下人类计算方式或计算技术的历史，就不难体会到计算方式是一种历史的结果，而非计算本性的逻辑必然。也就是说，计算之所以为计算，在于它具有一种根本的递归性，或在于它是一种可一步一步进行的符号串变换操作。至于这种符号变换的操作方式如何，以及符号的载体或其外在表现形式如何，都不是本质性的东西，它们元不是一种历史的结果，无不处于一种不断变革或进化的过程之中。不同表征下的符号变换有着不同的操作方式，甚至同一种表征下的符号变换都可以有不同的操作方式：既可以是物理性的方式，也可以是化学性的方式；即可以是经典的方式，也可以是量子的方式；既可以是确定性的方式，也可以是概率性的方式。在此，计算本质的统一性与计算方式的多样性得到了深刻的体现。笔者相信，DNA 计算机、量子计算机等的出现已经打开了人们畅想未来计算方式的思维视窗，随着科学技术的不断发展，计算方式的多样性还会有新的表现。其二，计算方式的历史性、多样性反观了计算本性的逻辑必然性、统一性。由丘奇- 图灵论点所揭示的计算本质是非常普适的，它不仅包括数值计算、定理推导等不同形式的计算，而且包括人脑、电子计算机等不同“计算器”的计算。大家不要忘了，以丘奇- 图灵论点为基石的可计算性理论是在电子计算机诞生之前的1930 年代提出的，即它并非在对电子计算机进行总结与抽象的基础上提出，但又深刻地刻画了电子计算机的计算本质。如今最先进的电子计算机在本质上就是一台图灵机，或者凡是计算机可计算的函数都是一般递归函数。现在人们又进一步认识到，目前尚在实验室阶段的DNA 计算机、量子计算机，在本质上也是一种图灵计算。这说明不同形式的计算、不同“计算器”的计算，在计算本质上是一致的，这就是递归计算或图灵计算。

zan