计算理论

计算理论（Theory of computation）是数学的一个领域，和计算机有密切关系。其中的理论是现代密码协议、计算机设计和许多应用领域的基础。该领域主要关心三个方面的问题：

- 采用什么计算模型（即形式语言、自动机）
- 解决哪些是可计算的、哪些是不可计算的（即可计算性理论及算法）
- 要用多少时间、要用多少存储（即计算复杂性理论）

这三方面的问题可以用一个问题来总括：“电脑的基础能力及限制到什么程度？”

计算理论的“计算”并非指纯粹的算术运算（Calculation），而是指从已知的输入透过算法来取得一个问题的答案（Computation），因此，计算理论属于理论计算机科学和应用数学。

为了对计算进行严谨的研究，电脑科学家会将计算以数学的方式抽象化，称为计算模型。有几种目前在使用的计算模型，其中最出名的是图灵机。电脑科学家研究图灵机的原因是它很容易叙述，可以分析，用来证明结果，而且用此模式呈现了许多强而有力的计算模型（参照邱奇－图灵论题）。图灵机有潜在的，数量无限的记忆能力，这似乎是不可能达到的，不过所有图灵机解决的可判定性问题都只需要有限量的记忆能力。因此理论上，任何可以用图灵机解决的（可判定性）问题都只需要有限量的记忆能力。

## 历史

计算理论早在所有计算机发明之前便开始了，当时是使用数理逻辑，在20世纪此理论和数学分离，成为一个独立的学科。

计算理论早期的重要贡献者有阿隆佐·邱奇、库尔特·哥德尔、艾伦·图灵、斯蒂芬·科尔·克莱尼、约翰·冯·诺伊曼及克劳德·香农等。

## 分支

### 自动机理论

文法｜语言｜自动机｜产生式（限制）

0-型文法｜递回可枚举｜图灵机｜$\alpha \rightarrow \beta$（无限制）

1-型文法｜上下文有关｜线性有界自动机｜$\alpha A \beta \rightarrow \alpha \gamma \beta$

2-型文法｜上下文无关｜非确定性下推自动机｜$A \rightarrow \gamma$

3-型文法｜正则｜有限状态机｜$A \rightarrow a$以及$A \rightarrow aB$

自动机理论研究抽象机器（或更贴切地说，抽象的“数学”机器或系统）以及可利用这些机器求解的计算问题。这些抽象机器称为自动机（automata）。“automata”一词源自希腊文（Αυτόματα），意指某物能自行运作（自动地完成某项动作）。

自动机理论也与形式语言理论密切相关，因为自动机往往依其能辨识的形式语言类别来分类。一个自动机可以是对某个形式语言的有限表示，而该形式语言本身可能是一个无限集合。自动机被用作计算机器的理论模型，并常用于可计算性相关的证明。

#### 形式语言理论

<image>

形式语言理论是数学的一个分支，关注如何以在字母表上的一组运算来描述语言。它与自动机理论紧密相连，因为自动机可用来生成与辨识形式语言。形式语言存在若干类别，每一类都允许比前一类更复杂的语言规格描述，例如乔姆斯基阶层，而且每一类形式语言都对应到一类能辨识它的自动机。由于自动机被用作计算的模型，对任何必须由计算完成的问题而言，形式语言往往是偏好的规格描述方式。

### 可计算性理论

可计算性理论主要处理一个问题：在多大程度上，一个问题能在电脑上被求解。“停机问题无法由图灵机求解”这一命题是可计算性理论中最重要的结果之一，因为它提供了一个具体问题的例子：形式化描述相对容易，但却不可能用图灵机加以解决。可计算性理论的许多内容都建立在停机问题的结果之上。

可计算性理论的另一个重要里程碑是莱斯定理（Rice's theorem）。该定理指出：对所有偏函数（partial function）的任何非平凡性质，要判定某台图灵机是否计算出具有该性质的偏函数，是不可判定的。

可计算性理论与数理逻辑中的递归论分支关系密切；递归论不再局限于只研究那些可化约至图灵模型的计算模型。许多研究递归论的数学家与计算理论学者，也会将其称为可计算性理论。

### 计算复杂性理论

<image>

计算复杂性理论不仅关心一个问题是否能在电脑上被解出，也关心该问题能否被有效率地解出。主要考量时间复杂度与空间复杂度两个面向，分别对应于完成一次计算所需的步骤数，以及完成该计算所需的内存量。

为了分析某个算法所需的时间与空间，电脑科学家通常把解决问题所需的时间或空间，表示为输入规模的函数。举例来说，在一串很长的数列中寻找特定数字，会随着数列变长而变得更困难。若我们说列表中共有 $n$ 个数字，且列表既未排序也未以任何方式建立索引，那么为了找到目标数字，我们可能必须逐一检查每个数字。因此可以说，解决这个问题所需的步骤数，会随问题规模以线性方式成长。

为了简化这类分析，电脑科学家采用大 O 记号，使得我们能以函数的方式来描述并比较效率：不必把机器实作的细节纳入考量，而是着重于问题规模变大时的渐近行为。因此在前述例子中，我们会说该问题需要 $O(n)$ 个步骤才能解决。

或许整个电脑科学中最重要的未解问题是“是否存在高效率的方法来解决一大类记为 NP 的问题”。相关内容可参见P = NP 问题，该问题是克雷数学研究所于2000年公布的七项千禧年大奖难题之一。该问题的官方叙述由图灵奖得主史蒂芬·库克提出。

## 计算模型

除了图灵机之外，还有其他等价（参见邱奇-图灵论题）的计算模型在使用。

$\lambda$-演算：一次计算由一个初始的 $\lambda$ 表达式（若要将函数与其输入分开，也可以使用两个）加上一个有限的 $\lambda$ 项序列所构成；序列中的每个 $\lambda$ 项，都可由前一个项经由一次$\beta$-归约推导而得。

组合子逻辑：是一个与 $\lambda$-演算有许多相似之处、但也存在重要差异的概念（例如，不动点组合子 Y 在组合子逻辑中具有正规形，但在 $\lambda$-演算中则没有）。组合子逻辑是在相当宏大的企图下发展而来：理解悖论的本质、使数学基础在概念上更为精简、消除变数的概念（从而厘清其在数学中的角色）。

$\mu$-递回函数：一次计算由一个 $\mu$-递回函数（亦即其定义序列）、任意输入值，以及在该定义序列中出现的递回函数之输入与输出序列所构成。因此，若在递回函数 $f(x)$ 的定义序列中出现函数 $g(x)$ 与 $h(x,y)$，则序列中可能会出现如“g(5)=7”或“h(3,2)=10”之类的项。此序列中的每一个条目必须是某个基本函数的应用，或是由上方条目透过函数合成、原始递回或$\mu$-递回等方式推出。举例而言，若 $f(x)=h(x,g(x))$，那么要让“f(5)=3”出现，就必须在其先前出现如“g(5)=6”以及“h(5,6)=3”等项。只有在最后一项给出了该递回函数对输入值的计算结果时，计算才会终止。

马尔可夫算法：一种字串重写系统，以类似形式文法的规则对由符号组成的字串进行操作。

寄存器机：是一种在理论上颇具意义的电脑理想化模型，并有若干变体。在多数变体中，每个寄存器都能储存一个任意大的自然数，而其指令少又十分简单，例如：只包含递减（结合条件跳转）与递增（以及停机）等操作。相较于图灵机所见的无限（或可动态增长的）外部储存空间，其欠缺可理解为以哥德尔编号技术取代该角色：由于寄存器能保存任意大的自然数，因此可以用哥德尔数来表示复杂的结构（例如序列、矩阵等）。而表示与诠释的明确性，则可由这些技术的数论基础加以建立。

除了上述一般性的计算模型之外，某些更简单的计算模型也适用于特定、受限的应用。例如，正规表示式可在许多情境中用来指定字串模式，从办公室生产力工具到程式语言皆然。另一种在数学上与正规表示式等价的形式系统是有限状态自动机，常用于电路设计以及某些类型的问题求解。上下文无关文法用于指定程式语言的语法；非确定性下推自动机则是与上下文无关文法等价的另一种形式系统。原始递回函数是递回函数的一个已定义子类别。

不同的计算模型能完成不同的任务。衡量某个计算模型能力的一种方式，是研究该模型能生成的形式语言之类别，如此便可得到语言的乔姆斯基阶层。

## 外部链接

- Theory of Computation at MIT
- Theory of Computation at Harvard
- Computability Logic - A theory of interactive computation. The main web source on this subject.