理论计算机科学

[拼音]：lilun jisuanji kexue

[外文]：theoretical computer science

信息加工的数学理论，又称为计算理论或计算机科学的数学基础。

计算是信息加工或信息活动的过程。反之，在广泛的意义上讲，任何一种形式的信息加工或信息的活动(包括大脑的思维活动中的信息加工和信息活动）都可以看作是一个计算的过程。信息的表示与信息的加工要有一个物质载体，但是并不一定要依赖于某一个特定的载体。不同载体上的信息活动又有其共性。由于信息加工的普遍性和相对于载体的独立性，以信息加工为研究对象的理论计算机科学必然是一门抽象的精密科学。它广泛地采用数学的方法，因此在某种意义下可以看成是数学的一个分支。

理论计算机科学最早的分支是20世纪30年代发展起来的可计算性理论。随着40年代计算机科学技术的迅猛发展，在60年代前后相继发展了自动机与形式语言理论，程序设计和形式语义理论，以及算法分析与计算复杂性理论。这些学科构成了目前理论计算机科学的主要内容。它是一门年轻的学科，正在迅速地发展。

可计算性理论

计算的本质是什么？什么样的问题是可计算的？什么样的问题是不可计算的？这些应当算作是理论计算机科学中最根本的问题。谈论问题的可计算性，总是就一个问题类而言的，而这个问题类中原则上应包含无穷多个个别问题。比如说，求两数的乘积就是一个问题类，求3与7或4与6的乘积则是这类问题中的一些个别问题。说乘法是可计算的，意思是能够给出一个统一的机械的办法去解决这个问题类中的任何问题。所谓一个统一的机械的办法至少应该是：

（1）每一步都是完全确定的。

（2）每一步都是机械地可执行的。

（3）在有限步之内得到答案。

（4）这个统一的办法本身有一个有穷的描述。这些条件要求计算是一个严格精确的过程。但这些条件本身却是很不精确。为了精确地刻画计算的过程，A.M.图灵提出了一个计算的数学模型，后来被称为图灵机器。这个机器由一个有穷的控制器和一条两边无限长的带组成，带上分成一串方格，每格中可以写上一个符号。控制器有一个读写头指向带上某方格，可读到格中的符号，并把它改写成另一个符号，还可以左移或右移一格。有穷控制器在任何时刻都处在有穷多个状态中的某个状态。它总是根据目前所处的状态q(∈Q)和读到的符号α(∈)决定把这个符号改写成什么符号b(∈)和自己该转入哪个状态 q┡(∈Q)以及读写头是否向左移一格(l)或向右移一格 (R)或停留不动(S)。如果开始计算时机器处于开始状态q₀，并把要计算的问题放在带上，让机器一步一步地执行下去，最后在带上就应该得到计算的答案。机器的有穷控制可以用列表的方法表示，表中的每一项都有

q，α→q┡，b，D

的形状，其中D为R，l，S之一。这个表就是所谓的统一的机械的办法，也就是程序。

图灵机器还可以推广成具有多条带的图灵机器。这时它有一条输入带，一条输出带，k条工作带。每条带上有一个读写头联向有穷控制。它根据当前状态以及输入带和k条工作带上目前被扫描的符号，决定下一步应转到什么状态，应该在k条工作带上和输出带上写下什么符号，以及各个读写头的移动方向。

图灵在设计了上述的单带的模型后提出：凡是可计算的函数都可以用这样一个机器来实现。这就是著名的图灵论题。A.丘奇在提出λ演算时也说，可计算的函数都是λ可定义的，这就是丘奇论题。而后S.C.克林证明这两个论题是等价的，以后称之为图灵-丘奇论题。这一论题本身是不能用数学方法加以证明的，只能够为历史所检验。半个世纪以来，数学家提出的各种各样的合理的计算模型都被证明是和图灵机器等价的。这一论题已被当作公理一样地使用着，它不仅是计算机科学的基础，也是整个数学的基石之一。

给了一个有穷字母表后，它上面所有"字"（字母的有限序列）的集合记为^*。^*的任何子集l(^*)称为上的一个语言。如果有一个图灵机T，使得对于任何输入字w ∈^*，T 都在有穷步之内停机，并且停机时，T 处于一个特殊的接受状态q_α当且仅当w∈l，就说l是可判定的。如果有一个图灵机T，从空白带开始无穷地运行下去，可以把l中的字一个不漏也不多余地写在带上，就说l是可枚举的。

可判定的语言一定是可枚举的。因为如果L中的每个字可判定，就可以依次把属于l的字枚举出来。另外，l是可判定的当且仅当l和l在^*中的补集^*-l都是可枚举的。因为若l可判定，则^*-l当然可判定，因而都是可枚举的。逆之，若l和^*-l都可枚举，则不难同时运行两台机器，分别枚举l和^*-l中的字，于是任何输入字w，迟早总会被其中一台枚举出来。因此总能判定w是属于l还是不属于l。

不难证明，图灵机的字母表中的元素的多少是无关紧要的。一般讲，有两个字母｛0，1｝再加上空格就足够了。每个图灵机T的程序总可以用0，1来编码，记为C_T。T从空带开始运行，枚举出某些0，1上的字。那么存在两种相反的可能性：

（1）T 终究会枚举出C_T；

（2）T 永远不枚举出C_T。把所有满足条件(2)的C_T放在一起，构成集合l=｛C_T｜T不枚举C_T｝。可以断定l是不可枚举的。因为若不然，则有一个图灵机T₀枚举l。设T₀本身的编码是C掱。那么，T₀是否能枚举出 C掱呢？如果 T₀枚举 C掱，则C掱应属于 l，于是T₀不应该枚举C掱， 矛盾。反之，如果T₀ 不枚举C掱，则C掱属于l， 于是 T₀又应该枚举C掱，同样得到矛盾。所以，枚举l的图灵机T₀是根本不能存在的。换言之，l不是可枚举的，因此更不可判定。以上的证明方法叫做对角线方法。

由l的不可判定性出发，可以得到许多数学问题的不可判定性。例如，停机问题不可判定，波斯特字的对应问题不可判定，群上字的问题不可判定，希尔伯特第10问题（代数不定方程是否有解问题，见希尔伯特数学问题）不可判定等等。具有加法和乘法的算术是不可判定的，即不能判定任一给定的算术命题是否为一条定理。谓词逻辑（见一阶逻辑）也是不可判定的。

自动机与形式语言理论

一个图灵机器可以看作为在某种环境下工作的一个有穷控制器。它的环境包括输入、输出带和k条工作带。如对环境作某些限制，就可得到各种各样的自动机。

如果限制工作带的总长不超过输入字的长度，就得到线性有界自动机；限制工作带的数目k=1，输入带头只许向右移动，并且工作带头右方的符号不保留，就得到栈自动机；限制输入输出带头都只能向右移动，并且没有工作带，就得到有穷自动机。栈自动机如果要读工作带上的一个符号，就必须把其右的符号全部丢掉。这就好象要从子弹夹里取出一颗子弹就必须先把它上面的子弹全部拿走一样。如果把工作带画成一个子弹夹，栈自动机的工作方式如图1所示。

一个有穷自动机的工作方式则如图 2所示。

如果有穷控制器在任何一个时刻，它的下一动作都是完全确定的，就说它是确定型的。否则，如果存在若干种可能的选择，就叫做非确定型的。

自动机常作为一个语言接受器来研究，这时，输出带没有什么意义。自动机有若干个接受状态。对于确定型的自动机而言，给了输入字w以后，机器一步步动作下去，如果机器最后停机并且停在一个接受状态，就说机器接受了字w，否则就说机器拒绝了w。所有被机器接受的字的集合称为机器接受的语言。对于非确定型的自动机而言，就存在着不同的计算路径的选择。有的路通向一个接受的状态，有的则不然。这时如何定义机器的接受与否，有不同的方式。

一种最自然的方式就是：只要存在一条通向某接受状态的路，就算机器接受了输入，这种方式一般叫做（狭义的）非确定型。也可以这样来规定：当所有的路都通向某个接受状态时才算机器接受了输入，这种方式叫合取型。还可以把所有的状态分成甲乙两类，如果机器在甲类状态有几种可能的选择，则只要求存在一种接受的选择，如果在乙类状态有几种可能的选择，则要求所有的选择都是接受的，这种混合情况称为交错型。还可以这样规定：凡碰到有多种可能选择的情况就用某种随机的办法(例如掷骰子)来确定一个选择，若这样计算下去达到一个接受状态的概率大于1/2就认为机器接受w 。否则，从接受概率不大于1/2可推出接受概率为0，机器拒绝w。这种类型叫随机型。合取型、交错型、随机型等也都是非确定型。但一般说，非确定型常指狭义的非确定型。

自动机在另一个方向上的推广，就是多个自动机组合成大的自动机，其中各个部分都在不断地并行工作。这种自动机的研究对于并行计算和模拟生命现象很有意义。硬件可修改机器(HMM)是一个有趣的例子。

HMM起初只有一个细胞，它可以发育成许多个互相联结在一起的细胞群。每个细胞都是一个完全一样的有穷自动机。每个细胞在任何时候都处于某个状态q∈Q，这里Q是一个有穷的状态集合。每个细胞有k个突触，联向它的“邻居”，也可以联向自己。根据它自身的状态以及它的邻居的状态，每个细胞可以做下面几件事情：

（1）改变到某个新状态；

（2）把自己的突触从现在的某邻居移到该邻居的某个邻居（因此变成新的邻居）；

（3）若有某个突触指向自己则可以分裂出一个和自己完全一样的“儿子”，把该突触指向儿子，儿子的所有突触指向自己，并令儿子处在某特定状态。

如果把HMM当作一个计算模型，可以假定输入的字符串是放在一棵二叉树的叶子上（图3

），这棵二叉树的每个结点（图中用圈表示）都是一个“死的” HMM细胞，即在计算过程中它们的状态和联结方式（图中用双向箭头表示）都不变化。只有树根上（图的下方）联着的那个细胞是“活的”，可以发展成许多细胞，并且把自己的突触伸到树叶上（图的上方）去读取输入信息。

HMM是具有很强功能的一种模型。如果取消它的第二种功能，再加以种种限制，就得到各种l系统，在描述生命的发展过程时很有用处。如果取消它的第二、三两种功能，并且假定整个的细胞网络的编码由一架图灵机给出，并且每个细胞都是某个逻辑门，就得到聚合的模型。把它布线在平面上就得到超大规模集成电路(VLSI)的模型。如果在某一维数的空间格子上布线，且假定只有相邻的格子才有联系，就得到各种细胞自动机的模型。

和自动机理论密切相关的是形式语言理论的研究。1956年，N.乔姆斯基创立了形式语法。1960年算法语言ALGOL-60的报告使用了巴科斯范式(BNF)来描述。此后形式语言学的研究便蓬勃发展了起来。

在形式语言学中，一个语法G由四部分组成G=(，V，S，P)，其中是字母表；V是和不相交的变元表；S是V 中的一个变元，称为初始符号；P是一组产生式，每个产生式都有形状α →β，其中α和β 都是混合字母表∪V上的一个字，α 至少要含有V中的一个变元，而β可以是长度为0的空字，α→β意为用β来代换α。这种语法称为一个0型文法。下面是语法的一个例子：

={α，b，( ， )，+，*}，

V={S}，

P={S→(S)，S→S+S，S→S*S，S→α，S→b}。

从初始符号S出发，不断用产生式代换，一直到全部由中的字母组成，就得到一个上的字。下面是一种可能的代换过程：

S→S*S→S*(S)→S*(S+S)

→α*(S+S)→α*(b+S)→α*(b+α)。

所有能这样推演出来的字就构成了一个语言，叫做该语法所生成的语言。

如果限制 β的长度不小于α的长度，则得到1型语法（又称上下文有关语法）；若限制 α仅由一个变元组成，则得到2型语法（又称上下文无关语法）;若再进一步限制产生式右端的β 为αB或α 的形式，其中α∈，B∈V，则得到 3型语法（又称正规语法）。由0、1、2、3型语法所生成的语言分别称为0、1、2、3型的语言。它们恰恰是图灵机器、非确定线性有界自动机、非确定栈自动机、有穷自动机接受的语言。

各类语言可以作各种代数运算。例如，求交(l₁∩l₂)，求并(l₁∪l₂)，求补(^*-l)，克林闭包，同态，代换，商，等等。研究各类语言在代数运算下的封闭性是形式语言理论中的一个方向。

给定了一个语法之后，自然要问它是否具有某种性质。例如两个语法是否定义了同一个语言?对于0、1、2型语法，这一问题是不可判定的，但对3型语法则是可判定的。在这一方向上有丰富的成果。

对于自动机和形式语言的研究，已形成了一些抽象的代数理论，例如自动机的半群理论、范畴理论等等，并取得了一些积极的成果。

程序设计方法与形式语义学

为了达到某种目的， 如何编出一个程序？编出程序以后又如何证明该程序的确能达到预期的目的？这是一个在实践中具有十分重要意义的问题。例如要求非负整数x₀和y₀的最大公因子，可以采用下面的程序：

符号(x，y)←(x₀，y₀)的意思是同时把x₀和y₀的值赋给x和y。因此若一开始(x₀，y₀)=(6，10)，那么(x，y)的变化情况为(6，10)→(6，4)→(4，6)→(4，2)→(2，4)→(2，2)→(2，0)→(0，2)。最后输出y=2，它是6和10的最大公因子。但这个程序为什么总能给出x₀和y₀的最大公因子并不是很显然的。另一方面，若把其中

改为

程序就不再是正确的。这是因为对于某些输入而言，程序不停机。而这一点也不是立即可以看出来的。因此程序的正确性需要证明。

所谓证明程序正确，就是要证明：若程序P的输入满足某种输入断言，则经过P作用之后的输出满足某个输出断言。在上面的例子中，输入断言可表示为

x₀≥0并且y₀≥0并且（x₀≠0或y₀≠0）。

输出断言可表示为

。

为了证明上面程序的正确性，在标号mOre处引进一个不变的性质：

x≥0并且y≥0并且（x≠0或y≠0）

并且

。

然后用归纳法证明每次程序执行到more时，上面的不变式都成立。因而， 执行到enouH时， 就满足输出断言。如果能证明上面的程序的确会停机，就证明了它的正确性。

数理逻辑对于程序设计方法的应用主要有下面四个方面：

（1）程序正确性证明；

（2）停机证明　证明一个程序终于会停机；

（3）程序展开　从给定的输入输出断言出发，逐渐构造出一个正确的程序；

（4）程序优化　从一个给定的程序出发，构造出一个等价的但更优的程序。

以上各方面的研究对程序设计的理论和实践都有着非常积极的意义。但是另一方面，由于k.哥德尔的不完备性定理，以及不可判定性的结果，以上问题的彻底解决是非常困难的甚至是不可能的。它们的困难程度可从下面的例子看出来。

也就是说，如果整数x是偶数则除以2，否则乘3再加1。对于小于3×10⁸的所有的数，可以知道最后的x都会变成1而停机。但是尚不知道，上面的程序是否对于任意的x都会终止（x变成1）。

为了证明程序的正确性，对程序的性质作深入的研究，还发展了形式语义学。形式语义学目前主要有操作语义学、指称语义学、代数语义学和公理语义学等分支。

操作语义学把语言的语义看做是在计算系统中所执行的某种操作。这种操作应当被理解为在一种标准的抽象的机器上执行的，而不依赖于一个特定的机器。以算术表达式的求值为例，就是假定了一个抽象机器，它有栈区、环境区和控制区三个存储区。把这三个区中的内容用两个竖杠分开，再用括号括起来，就表示了机器的一个状态。例如

表示栈区为空，环境区有数据1，2，5分别代表x₁，x₂和x₃的当前值，控制区放有符号串(x₁+x₂)*x₃。算术表达式求值的语义可由下面四大类状态转移规则给出：

（1）

（2）

（3）

（4）其中St，E，C分别代表栈区、环境区和控制区中的某些内容。第一个式子表示，若控制区的第一串符号是(e₁，Op，e₂)或e₁Op e₂的形状，其中e₁，e₂是表达式，Op是运算符，那么把它拆开成e₁，e₂，Op三串符号，放在控制区的前面，其余内容不动;第二个式子说，若控制区的第一个符号串是某个自然数n，则把该自然数的表示n送入栈区的第一个位置；第三个式子说，若控制区的第一个符号串是变元x_i，则把环境区中第i个值e_i放入栈区（因为它代表x_i的当前值）；最后一个式子说，若控制区的第一串符号是某运算符Op，则把栈区中前两个值m和n作相应的运算，得到值mOpn=k，把k放入栈区第一个位置。

上面例子的相应操作如下：

意为表达式(x₁+x₂)*x₃在环境x₁=1，x₂=2，x₃=5下语义为执行上述一系列的操作，最后得到15。

在操作语义学中，如果操作的次序不同，尽管操作的结果相同，也被认为具有不同的语义。但在指称语义学中，结果相同就认为具有相同的语义。所以指称语义学只是关心语句引起的状态的改变。如果用Statements表示所有语句的集合，语义就是一个从Statements到状态集合State的改变之间的映射，也即一个映射C：

C: Statements→(State→State)。

用代数方法和公理化方法研究形式语义，又形成了代数语义学和公理语义学。以上四种语义虽然已取得了很大进展，但是，只有操作语义学可以较好地描述程序的语义。

复杂性理论和算法分析

可计算性理论在逻辑上的进一步发展，就是计算复杂性理论。著名的图灵-丘奇论题说，凡是合理的计算模型都是等价的，即一个模型能计算的，在别的模型下也能计算，否则都不可计算。但是对于一个问题类而言，只知道能不能计算是很不够的，更有实际意义的是要知道计算需要多少时间，多大的内存等等。由此产生了计算复杂性理论和算法分析。

计算所需的时间、存储大小等等都算为资源。严格地讲，每一种资源的定义都依赖于一个计算模型。各种计算模型的资源的定义虽不一样，但是主要的有三种。

（1）串行时间　简称时间， 它是计算过程中的总运算量。也即把计算分成一些原始的步骤，完成这些步骤所需的总时间。

（2）空间 它是为了保存计算的中间结果所需地盘的大小。例如在计算时用一块黑板来打草稿，假定每一单位黑板面积可以写一个符号，且可以擦掉重写，空间就相当于打草稿所需的黑板面积。

（3）并行时间 即并行计算所需的时间。也即多人或多机协同计算，解决一个问题所需要的时间。

复杂性总是对于一个特定的问题类来讨论的，其中包括无穷多个个别问题，有大有小。例如对矩阵乘法这一问题类而言，相对地说100阶矩阵相乘就是一个较大的问题，而二阶矩阵相乘则是个较小的问题。所以可以把阶n作为衡量问题大小的尺度。但是最一般地，是把输入的总长度n作为问题大小的尺度。因此，当给定一个算法以后，计算一个大小为n的问题所需的时间、空间等就可以表为 n的函数。这个函数就叫做该算法的时间或空间的复杂性之度量，或称为复杂度。严格地讲，它是这个特定的问题类在某一特定计算模型中的某一算法下的复杂度。当要解决的问题越来越大时，时间、空间等资源的耗费将以什么样的速率增长，也即当n趋于无穷时这个函数增长的阶是什么？这就是复杂性理论所关心的问题。

在计算同一个问题类时，算法有好坏之别。例如要判定一个具有n个顶点的无向图中有没有回路，早期的算法所需的空间复杂度为S(n)=O(log²n)，但是后来设计了更精细的算法，它的空间复杂度只有O（logn）。这说明O（log²n）只是早期算法的空间复杂度，而并非这个问题本身的内在复杂度。或者说O（log²n）只是回路问题空间复杂度的一个上界，而O（logn）则是一个新的更好的上界。对于回路问题，任何算法都至少需要正比于logn的工作空间。这就是说，对于任何算法，空间复杂度S(n)=Ω(logn)。因此可以认为Ω(logn)是回路问题空间复杂度的一个下界。问题内在的复杂度介于上界和下界之间。在这个例子中，二者重合了。因此可以说回路问题的空间复杂度正比于logn，记为S(n)=嘷(logn)。

又如两个n位二进整数的乘法在多带图灵机模型下，一般的算法需时O(n²)。但改进的算法可以达到O(n^1.5)。现在最好的算法可以达到O(nlognloglogn)。如果采用存储可修改机器做模型，则可以达到O(n)。可以看出一个问题的内在计算复杂性还因计算模型的不同而有高低。

较为重要而且具有特色的计算模型主要有多带图灵机器，多带多维多头图灵机器，硬件可修改机器（HMM），随机存取机器(RAM)，并行随机存取机器(PRAM)，向量机器，VLSI，等等。然而没有一个适合一切问题的统一的模型。这样，复杂性的问题有没有一个相对统一的标准呢？相似性原理解答了这一问题。按此原理，计算一个问题类使用的并行时间、空间和串行时间的复杂程度在所有理想的计算模型中都没有本质的差异。用数学语言来说，各种模型不仅可以相互模拟而且模拟者所需的并行时间、空间和串行时间都分别不超过被模拟者需用的并行时间、空间和串行时间的一个多项式。所以在只差一个多项式的范围内，复杂性还是有其客观依据而是不依赖于模型的。对于上面提到的各种模型，以及各种计算类型，相似性原理已被证明是正确的。

对于串行计算模型都可以定义一个虚拟的并行时间，叫做巡回。所谓巡回，是指计算过程中的周相数。而一个周相则是计算过程中的一个阶段，在此阶段中新计算出来记在工作空间上的信息不准在同一阶段内被读到。例如，对于多带图灵机器而言，一个周相就是工作带头不改变方向的一段时间。所以巡回相当于工作带头改变方向的总次数。因此可以说，一个问题类有快速的并行算法当且仅当它有一个具有小的巡回数(虚拟并行时间)的串行算法。另外并行时间和空间之间具有某些对称的性质。例如可以证明，它们之间是多项式相关联的。所以说，一个问题类有一个快速并行时间算法当且仅当它有一个高度节省内存的算法。

既然在多项式关联意义下复杂性不依赖于模型，就可以用P代表所有具有多项式时间算法的问题类;用NP代表所有具有非确定多项式时间算法的问题类；用NC代表所有能同时在对数多项式并行时间和多项式空间解决的问题类；等等。

一般认为，P中的问题才具有现实的可计算性，但有许多实际问题属于NP，却未能找到一个确定型多项式时间算法。所以许多人猜想PNP。1971年库克在NP中找到一个问题类，叫做布尔合取范式的可满足性问题(SAT)。证明了NP中任何一个问题类的计算均可归约为SAT的计算。因此，称SAT为一个NP完全性问题（见组合最优化），NP=P当且仅当对SAT存在一个确定型多项式时间的算法。以后C.卡普等人又把SAT归约为许多其他的组合问题，得出了许多其他的NP完全性问题。目前NP完全性问题几乎涉及到一切数学的分支，形成了一个专门的理论。但是NP是否等于P的问题尚未解决。有人猜想它是独立于现有的数学公理系统的。完全性的研究不限于NP完全性。对于各个复杂性类，都有完全性问题。

在复杂性基本理论的基础上，对各类具体数学问题的复杂性研究构成了算法分析的主要内容，60年代以来取得了长足的进展。例如n维的快速傅里叶变换和n次多项式的乘法， 只需要O(n logn)次算术运算；n位的数乘在多带图灵机上只需O（nlognloglogn）的时间;判定一个n位数是否为素数需时O()；在出度限定情况下，图同构的判定问题存在多项式时间的算法；判定整系数线性规划问题是否存在有理解，存在多项式时间算法；n阶矩阵乘法只需4.7n^2.8次算术运算;后来又改进为O(n)，还证明了，这个阶可以无穷地改进下去，等等。

对比于上界的情况，下界的研究却碰到了许多困难，尤其是对一些具有实际意义的问题。例如对任何一个NP完全性问题，猜想至少需要指数的时间，但多年来连一个非线性的下界都证不出来。

除了计算的复杂性，还有描述的复杂性，这是α.η.柯尔莫哥洛夫和察廷提出来的。 一个01串w 的信息量I(w)被定义为输出w 的最小程序的长度。因为各个模型可以互相模拟，故以上的定义在只差一个常数值的意义下，是不依赖于模型的。因为任何一个数学公理系统所包含的信息量是有限的，因而在这个系统中不可能证出I(w)≥с形的定理，这里с是只依赖于公理系统的一个常数。但容易知道，除了有限多个w 以外，所有的w 都满足I(w)≥с（却无一能被证明）。这一结果简化和加强了哥德尔不完备性定理。