gghhjj 发表于 2006-9-10 07:48

[转帖]理解计算

信人: 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 计算机、量子计算机,在本质上也是一种图灵计算。这说明
不同形式的计算、不同“计算器”的计算,在计算本质上是一致的,这就是递归计
算或图灵计算。
页: [1]
查看完整版本: [转帖]理解计算