可计算性和复杂性（一）

1. 原则上可以计算什么？简介和历史

2. 图灵机

2.1 通用机器

2.2 停机问题

2.3 可计算函数和可枚举性

2.4 停机问题的不可解性

3. 原始递归函数

3.1 递归函数

4. 计算复杂性：实践中的可计算函数

4.1 归约和完整性

4.2 复杂性的意义

参考书目

学术工具

其他互联网资源

相关条目

1. 原则上可以计算什么？简介和历史

在 20 世纪 30 年代，早在计算机出现之前，来自世界各地的各种数学家就发明了精确、独立的可计算定义。阿隆佐·丘奇定义了 Lambda 演算，库尔特·哥德尔定义了递归函数，斯蒂芬·克莱恩定义了形式系统，马尔可夫定义了后来被称为马尔可夫算法的东西，埃米尔·波斯特和艾伦·图灵定义了现在被称为波斯特机和图灵机的抽象机器。

令人惊讶的是，所有这些模型都是完全等价的：任何在 Lambda 演算中可计算的东西都可以用图灵机计算，对于上述计算系统的任何其他对也是如此。在证明了这一点之后，丘奇表达了这样的信念：“原则上可计算”的直观概念与上述精确概念相同。这种信念现在被称为“丘奇-图灵论题”，被数学家们一致接受。

编纂可计算内容的部分动力来自数学家大卫·希尔伯特。希尔伯特认为，所有数学都可以精确地公理化。一旦完成此操作，就会有一个“有效程序”，即一种算法，它将任何精确的数学语句作为输入，并在有限步骤后判断该语句是真还是假。希尔伯特要求现在称为所有数学的决策程序。

作为这个决策问题的一个特例，希尔伯特考虑了一阶逻辑的有效性问题。一阶逻辑是一种数学语言，大多数数学语句都可以用它来表述。一阶逻辑中的每个语句在每个适当的逻辑结构中都有精确的含义，即它在每个这样的结构中为真或为假。在每个适当结构中为真的那些语句被称为有效的。在某些结构中为真的那些语句被称为可满足的。请注意，公式φ有效当且仅当它的否定¬φ不可满足。

希尔伯特将一阶逻辑的有效性问题称为entscheidungsproblem。在希尔伯特和阿克曼合著的教科书《数理逻辑原理》中，作者写道：“当我们知道一个程序，允许任何给定的逻辑表达式通过有限多次运算决定其有效性或可满足性时，判定问题就解决了……判定问题必须被视为数理逻辑的主要问题。”（Böerger、Grädel 和 Gurevich 1997）。

哥德尔在 1930 年的博士论文中，基于怀特黑德和罗素的《数学原理》（Gödel 1930），提出了一阶逻辑的完整公理化。哥德尔证明了他的完备性定理，即公式只有当其有效时才可以从公理中证明。哥德尔的完备性定理是解决希尔伯特判定问题的一步。

具体来说，因为公理很容易识别，而推理规则非常简单，所以有一个机械的过程可以列出所有的证明。注意，证明中的每一行要么是公理，要么通过一条简单规则从前几行得出。对于任何给定的字符串，我们都可以判断它是否是证明。因此，我们可以系统地列出所有长度为 1、2、3 等的字符串，并检查其中的每一个是否都是证明。如果是，那么我们可以将证明的最后一行添加到我们的定理列表中。用这种方式，我们可以列出所有的定理，也就是说，通过一个简单的机械过程就可以列出所有一阶逻辑的有效公式。更准确地说，有效公式集是可计算函数的范围。用现代术语来说，我们说一阶逻辑的有效公式集是递归可枚举的（r.e.）。

然而，哥德尔的完备性定理不足以给出判定问题的正解。给定一个公式φ，如果φ有效，则上述过程最终会将其列出，从而可以回答“是的，φ有效”。但是，如果φ无效，那么我们可能永远找不到这个事实。缺少的是一个列出所有无效公式的程序，或者等效地列出所有可满足公式的程序。

一年后，即1931年，哥德尔证明了他的不完备性定理，震惊了数学界：自然数一阶理论没有完整且可计算的公理化。也就是说，没有合理的公理列表，我们可以从中精确证明数论的所有真实陈述（Gödel 1931）。

几年后，丘奇和图灵独立证明了判定问题是不可解的。丘奇通过使用哥德尔不完备定理的方法来证明一阶逻辑的可满足公式集不是真实的，即它们不能通过可由 lambda 演算计算的函数系统地列出。图灵介绍了他的机器并证明了许多有趣的定理，其中一些我们将在下一节讨论。特别是，他证明了停机问题的不可解性。他得到了判定问题的不可解性作为推论。

希尔伯特非常失望，因为他为所有数学制定的决策程序计划被证明是不可能的。然而，正如我们将在本文的其余部分更详细地看到的那样，人们对计算的基本性质有了很大的了解。

2. 图灵机

在 1936 年的论文“论可计算数及其在判定问题中的应用”中，艾伦·图灵介绍了他的机器并建立了它们的基本属性。

他清晰而抽象地思考了机器执行计算任务意味着什么。图灵将他的机器定义为由以下部分组成：

一个有限集合 Q，包含可能的状态，因为任何设备都必须处于有限多个可能状态之一；

一个可能无限的磁带，由某个有限字母表 Σ 中的连续单元 σ1、σ2、σ3 组成；

（Σ 可以是任何包含至少两个符号的有限集合。固定 Σ={0,1,b} 很方便，它由二进制字母表加上空白单元符号组成。我们通常假设磁带的有限初始段包含二进制符号，其余部分为空白。）

一个读/写磁带头 h≥1，扫描磁带单元 σh；最后，

一个转换函数 δ:Q×Σ→Q×Σ×{−1,0,1}。

（转换函数的含义是，从任何给定状态 q 看任何给定符号，σh,δ 告诉我们机器应该进入的新状态、应该在当前方块中写入的新符号以及新的头部位置 h′=h+d，其中 d∈{−1,0,1} 是 δ 给出的位移。）

与随机存取存储器相反，其存储带的线性特性限制了计算速度，但不是功率：图灵机可以找到任何存储位置，即磁带单元，但这可能很耗时，因为它必须沿着磁带一步一步移动头部。

图灵机的美妙之处在于该模型非常简单，但功能却非常强大。图灵机具有潜在的无限工作空间，因此它可以处理任意大的输入，例如将两个大数字相乘，但它每一步只能读取或写入有限量的信息，即一个符号。甚至在图灵机和所有其他计算数学模型被证明是等价的之前，在丘奇-图灵论题被提出之前，图灵就令人信服地论证说他的机器和任何可能的计算设备一样强大。

2.1 通用机器

每个图灵机都可以通过其转换表唯一地描述：对于每个状态 q 和每个符号，σ,δ(q,σ) 是新状态、新符号和头部位移。这些转换表可以写成一个有限的符号串，给出每个图灵机的完整指令集。此外，这些符号串可以按字典顺序列出如下：M1、M2、M3、…，其中 Mi 是图灵机编号 i 的转换表，即完整的指令集。Mi 的转换表是图灵机 i 的程序，或者更简单地说，是第 i 个程序。

图灵表明他可以构建一个通用的图灵机 U，即它可以运行任何其他图灵机的程序。更明确地说，对于任何 i 和任何输入 w，U 在输入 i 和 w 上所做的与 Mi 在输入 w 上所做的完全相同，以符号表示，

U(i,w)=Mi(w)

图灵构建的通用机器为计算提供了最基本的见解：一台机器可以运行任何程序。无论我们将来需要执行什么计算任务，一台机器都可以完成所有任务。正是这种见解使得制造和销售计算机成为可能。一台计算机可以运行任何程序。我们不需要每次遇到新问题时都购买一台新计算机。当然，在个人电脑时代，这个事实是一个如此基本的假设，以至于很难退后一步去欣赏它。

2.2 停机问题

由于图灵机被设计为包含所有可能的计算，因此它有一个不可避免的缺陷：某些图灵机在某些输入下永不停机。某些图灵机不会因为愚蠢的原因而停机，例如，我们可以对图灵机进行错误编程，使其陷入紧密循环，例如，在状态 17 中看到 1 时，它可能会转到状态 17，写入 1 并将其头部移位 0。稍微不那么愚蠢的是，我们可以到达一个空白符号，右边只有空白符号，但仍保持在同一状态，向右移动一步，寻找“1”。这两种不停机的情况都可以通过一个像样的编译器轻松检测和修复。但是，考虑图灵机 MF，它在输入“0”时，系统地搜索费马最后定理的第一个反例，并在找到后输出反例并停机。直到安德鲁·怀尔斯 (Andrew Wiles) 最近证明了费马大定理，世界上所有的数学家们，在三个多世纪的努力下，都无法确定当输入“0”时，MF 是否最终会停止。现在我们知道它永远不会停止。

2.3 可计算函数和可枚举性

由于图灵机可能不会在某些输入上停止，因此我们必须小心定义图灵机可计算的函数。设自然数 N 为集合 {0,1,2,…}，我们将图灵机视为从 N 到 N 的部分函数。

设 M 为图灵机，n 为自然数。如果 M 的磁带以数字 n 的二进制表示形式（没有不必要的前导 0）开头，后面只有空白符号，则我们说 M 的磁带包含数字 n。

如果我们在包含 n 的磁带上启动图灵机 M，并且它最终在包含 m 的磁带上停止，那么我们说 M 在输入 n 时计算 m:M(n)=m。如果我们在输入 n 上启动 M，它从不停止，或者当它停止时，它的磁带不包含自然数，例如因为它有前导 0，或数字中散布着空白符号，那么我们说 M(n) 在符号上未定义：M(n)=↗。因此，我们可以将每个图灵机 M 与一个部分函数 M:N→N∪{↗} 相关联。如果对于所有 n∈N，M(n)∈N，即 M(n) 始终是定义的，则我们说函数 M 是全函数。

现在我们可以正式定义集合可递归枚举（r.e.）的含义，我们之前已经非正式地描述过。设 S⊆N。则 S 为 r.e. 当且仅当存在某个图灵机 M，使得 S 是 M 计算出的函数的符号像，

S={M(n)∣n∈N;M(n)≠↗}。

因此，只有当 S 能被某个图灵机列出时，它才是 r.e.。假设 S 是 r.e.，并且其元素可由图灵机 M 如上所述枚举。然后我们可以描述另一个图灵机 P，当输入 n 时，它以循环方式在其所有可能的输入上运行 M，直到最终 M 输出 n。如果发生这种情况，则 P 停止并输出“1”，即 P(n)=1。如果 n∉S，则 M 永远不会输出 n，因此 P(n) 永远不会停止，即 P(n)=↗。

让符号 P(n)↓ 表示图灵机 P 在输入 n 时最终停止。对于图灵机 P，定义 L(P)，即 P 接受的集合，为那些数字 n，使得 P 在输入 n 时最终停止，

L(P)={n∣P(n)↓}。

上述论证表明，如果集合 S 是 r.e.，那么它被某个图灵机 P 接受，即 S=L(P)。该语句的逆命题也成立。也就是说，S 是 r.e.当且仅当它被某个图灵机接受，P。

我们说集合 S 是可判定的当且仅当存在一个全图灵机 M，它可以针对所有 n∈N 判定 n∈S 是否。将“1”视为“是”，将“0”视为“否”。对于所有 n∈N，如果 n∈S，则 M(n)=1，即输入 n 时的 M 最终停止并输出“是”，而如果 n∉S，则 M(n)=0，即输入 n 时的 M 最终停止并输出“否”。可判定的同义词有：可计算、可解和递归。

对于 S⊆N，S 的补集为 N−S，即所有不在 S 中的自然数的集合。我们说集合 S 是 co-r.e.当且仅当其补集为 r.e. 时，如果集合 S 为 r.e. 且 co-r.e.，那么我们可以在一列中列出其所有元素，在第二列中列出其所有非元素。这样，我们就可以确定给定元素 n 是否在 S 中：只需扫描两列并等待 n 出现。如果它出现在第一列中，则 n∈S。否则它将出现在第二列中，并且 n∉S。事实上，当且仅当集合为 r.e. 且 co-r.e. 时，集合才是递归的。

2.4 停机问题的不可解性

图灵问是否每个自然数集都是可判定的。通过以下计数论证很容易看出答案是“否”。N 有不可数个子集，但由于图灵机只有可数个，因此可判定集也只有可数个。因此几乎所有集合都是不可判定的。

图灵实际上构造了一个不可判定集。正如我们将看到的，他使用对角线论证做到了这一点。对角线论证可以追溯到格奥尔格·康托，他用它来证明实数是不可数的。哥德尔在证明不完全性定理时使用了类似的对角线论证，他在数论中构造了一个句子J，其含义可以理解为“J不是定理”。

图灵构造了一个对角线停机集K，如下所示：

K = {n∣Mn(n)↓}。

也就是说，K由那些在输入自己的程序时最终会停止的图灵机组成。

不难看出K是r.e。为了矛盾起见，假设 K 也是共线性的，并让 d 成为接受 K 补集的图灵机的数字。也就是说，对于任何 n，

n∉K⇔Md(n)↓

但是，考虑一下当我们在上面的等式中用 d 代替 n 时会发生什么：

d∉K⇔Md(d)↓。

但是，K 的定义告诉我们：

d∈K⇔Md(d)↓。

因此我们有

d∈K⇔d∉K，

这是一个矛盾。因此，我们关于 K 是共线性的假设是错误的。因此 K 不是递归的。因此，给定一个图灵机及其输入并决定图灵机是否最终会在该输入上停止不是一个可计算的问题，即停止问题是无法解决的。

3. 原始递归函数

我们接下来定义原始递归函数类。这是一个非常有趣的函数类，Skolem (1923) 在一篇论文中描述了它，哥德尔在证明不完备定理时使用了它。我们感兴趣的是函数 f，从 Nr 到 N，其中 r=0,1,2,…。这里 r 称为函数 f 的元数，即它所接受的参数的数量。哥德尔从三个非常简单的函数（初始函数）和两个自然闭包运算（组合和原始递归）开始，每个运算都采用一些已经定义的函数并使用它们来定义一个新函数。接下来我们将详细解释他的定义。本节是技术性的，可以放心跳过。重要的思想是，原始递归函数包含一个非常庞大且强大的可计算函数类，所有这些函数都是以极其简单的方式生成的。

我们从三个初始原始递归函数开始：

ζ，元数为 0 的零函数，ζ( ) = 0；

η，元数为 1 的恒等函数，η(n) = n；

σ，元数为 1 的后继函数，σ(n) = n+1。

现在考虑以下两个操作：

组合：如果 f 是元数为 a 的原始递归函数，g1,…,ga 是元数为 r1,…,ra 的原始递归函数，并且 k∈N，则以下是元数为 k 的原始递归函数：h(x1,…,xk) = f(g1(w1),…,ga(wa))，

其中每个 wi 都是来自 x1,…,xk 的 ri 个参数的列表，可能有重复；和，

原始递归：如果 f 和 g 分别是元数为 k 和 k+2 的原始递归函数，则存在一个元数为 k+1 的原始递归函数 h，满足以下条件：h(0,x1,…,xk)=f(x1,…,xk)；并且，h(n+1,x1,…,xk)=g(h(n,x1,…,xk),n,x1,…,xk)。

这里，组合是组合函数的自然方式，原始递归是一种受限的递归，其中第一个参数为 n+1 的 h 是根据第一个参数为 n 的 h 定义的，其他所有参数均保持不变。

将原始递归函数定义为包含初始函数并在组合和原始递归下封闭的最小函数类。原始递归函数集等于使用有界迭代计算的函数集（Meyer & Ritchie 1967），即在语言 Bloop 中可定义的函数集（Hofstadter 1979）。

原始递归函数的定义非常简单，但功能非常强大。哥德尔归纳证明，每个原始递归函数都可以在一阶数论中简单地表示。然后，他使用原始递归函数用数字对公式甚至公式序列进行编码。最后，他使用原始递归函数计算所表示公式的属性，包括公式是否格式正确以及公式序列是证明。

需要一系列很长的引理才能说明原始递归函数的强大功能。以下是一些示例，说明加法、乘法和幂运算是原始递归的。

定义加法函数 P(x,y) 如下：

P(0,y)=η(y)P(n+1,y)=σ(P(n,y))

（请注意，这符合原始递归的定义，因为函数 g(x1,x2,x3)=η(σ(x1)) 可以通过组合从初始函数 η 和 σ 定义。）

接下来，定义乘法函数 T(x,y) 如下：

T(0,y)=ζ( )T(n+1,y)=P(T(n,y),y)。

接下来，我们定义指数函数 E(x,y)。 （通常 00 被认为是未定义的，但由于原始递归函数必须是全函数，我们将 E(0,0) 定义为 1。）由于原始递归只允许我们在第一个参数上进行递归，我们使用两个步骤来定义指数函数：

R(0,y)=σ(ζ( ))R(n+1,y)=T(R(n,y),y)。

最后，我们可以通过组合定义 E(x,y)=R(η(y),η(x))。（回想一下，η 是恒等函数，因此可以更简单地写为 E(x,y)=R(y,x)。）

指数函数 E 增长非常迅速，例如，E(10,10) 为一百亿，E(50,50) 超过 1084（因此远远超过宇宙中估计的原子数量）。但是，存在增长速度更快的原始递归函数。正如我们所见，E 是从缓慢增长的函数 σ 定义的，使用了三种原始递归应用：一种用于加法，一种用于乘法，然后另一种用于指数运算。我们可以继续应用原始递归来构建一系列难以想象的快速增长函数。让我们在定义超指数函数 H(n,m) 的系列中再多一步，将其定义为 2 的 2 的 2 的 2 的 …… 的 m，其中有 n 个 2。H 是原始递归的，因为它可以通过再使用一种原始递归应用从 E 定义：

H(0,y)=yH(n+1,y)=E(2,H(n,y))

因此 H(2,2)=24=16,H(3,3)=2256 大于 1077，与宇宙中的原子数量相当。如果这对你来说还不够大，那么考虑 H(4,4)。要以十进制表示这个数字，我们需要一个 1，后面跟着比宇宙中粒子数量还多的 0。

3.1 递归函数

原始递归函数集是一类庞大的可计算函数。事实上，它们可以被描述为时间可计算的函数集，即某个 n 的原始递归函数，其中 n 是输入的长度。例如，由于 H(n,n) 是原始递归函数，因此原始递归函数包括 TIME[H(n,n)] 的全部。（有关包括 TIME 在内的计算复杂性的讨论，请参阅下一节。）因此，原始递归函数包括所有可通过任何可想象的可行度量进行可行计算的函数，甚至更多。