SEP：可计算性与复杂性（二）

2.4 The Unsolvability of the Halting Problem

图灵问到，对于所有自然数集来说是否其都是可判定的。通过下面的计数论证，我们非常容易地就能知道答案是否定的。N有不可数数量的子集，但由于我们只有可数数量的图灵机，所以也只有可数数量的集合是可判定的。那么最后就是，多数集合都是不可判定的。

图灵实际上构造了一个不可判定集。如我们将看到的那样，他是通过运用对角线法(diagonal argument)来做到的。对角线法可以追溯到康托尔用其去表明实数是不可数的。哥德尔在他对不完备性定理的证明中，也用了一个相似的对角线法，他在数论中构造了这样一个句子J，这个句子的意思是，它本身不可证。

图灵如下地构造了一个对角线式停机集K：

K＝{n│Mₙ(n)↓}.

这是指K由那些，输入它们自己的程序后最终会停机的图灵机所组成。

不难看到，K是递归可枚举的。为了构造矛盾，假设，K也是共递归可枚举的，并让d为接受K的元素的一台图灵机的数。这样，对于任何n，n ∉ K ⇔ Md(n)↓

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

d ∉ K ⇔ Md(n)↓

但K的定义告诉我们，

d ∈ K ⇔ Md(d)↓.

这样，我们就有了，

d ∈ K ⇔ d ∉ K

而这是一个矛盾，因此，我们对K是共递归可枚举的假设是错误的。也因此，K将不是递归的。这可以推出，对于一个给定的图灵机及其输入，并判定其最终是否能够停机的问题来说，这不是一个可计算问题，即，停机问题是不可解的。(译注：最先的定义告诉我们d属于K等价于Md输入d时停机，但因为，K是递归可枚举且共递归可枚举的，所以对于任何数n都可以使M停机而不管是其是否属于K，而当我们将d代到其不属于K的n的情况下时，其当然也可以停机，并等价推出d ∈ K，这样就出现了矛盾)

1. Primitive Recursive Functions

我们接下来定义*原始递归函数(primitive recursive functions)*的类(class)。这是一个非常有有意思的函数类，其由Skolem (1923)给出，并被哥德尔运用到了他对不完备性定理的证明中。我们关注于从Nʳ到N的函数f，对于r＝0，1，2，. . .，我们称r为函数f的元数，即其中变元的数目。哥德尔从三个非常简单的函数开始，初始函数，以及两个自然闭包运算，合成(composition)与原始递归，它们中都每一个都使用某个已经被定义好的函数，然后去定义一个新函数。下面我们将细节性地解释一下他的定义。这节将比较技术化，你跳过了也没啥关系。关键思想是，原始递归函数由一个非常大且强有力的可计算函数类组成，并且所有它们都以非常简单的方式被生成出来。

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

• ζ为，元数0的零函数(zero function)，ζ()＝0；

• η为，元数1的恒等函数(identity function)，η(n)＝n；以及

• σ为，元数1的后继函数(successor function)，σ(n)＝n＋1。

然后考虑下面两个运算：

• Composition：如果f是一个元数α的原始递归函数，以及g₁，. . .，gα为元数r₁，. . .，rα的原始递归函数, 并且k ∈ N，那么下面是一个元数k的原始递归函数：

h(x₁，. . .，xₖ)＝f(g₁(ω₁)，. . .，gα(ωα))

在其中，每个ωᵢ为，rᵢ变元的一个列表，来自于x₁，. . .，xₖ，并或许包含重复。

• Primitive recursion：如果f与g各自地为，元数k与k＋2的原始递归函数，那么我们有一个元数k＋1的原始递归函数h，其满足下面的条件：

h(0，x₁，. . .，xₖ)＝f(x₁，. . .，xₖ)；以及，

h(n＋1，x₁，. . .，xₖ)＝g(h(n，x₁，. . .，xₖ)，n，x₁，. . .，xₖ)。

在这里，合成是一种非常自然的方式以去合并函数，而原始递归函数是一种有限制的递归，其中第一个变元为n＋1的h根据，第一个变元为n的h来定义，而所有其他变元保持不变。

定义原始递归函数为，包含初始函数以及在合成与原始递归运算下闭合的函数的，最小类。原始递归函数的集等同于，使用有界迭代(bounded iteration)计算的函数的集(Meyer & Ritchie 1967)，即，在BlooP语言中可定义的函数集，这来自于(Hofstadter 1979)

原始递归函数有着非常简单的定义但却非常强大。哥德尔归纳性地证明了每个原始递归函数都可被简单地表达在一阶数论中。然后他使用原始递归函数去编码公式，甚至是公式的序列。最后他用原始递归函数去计算，被重新表达公式的性质，这包括，一个公式是合式公式，一个公式的序列是一个证明，以及一个公式是一个定理。

要用一长串的引理才能展示得了原始递归函数有多么强大。以下是一些个例子，其显示了加法乘法，及指数运算都是原始递归的。

定义加法运算函数P(x，y)，为如下：

P(0，y)＝η(y)

P(n＋1，y)＝σ(P(n，y))

(注意，这满足原始递归的定义，因为函g(x₁，x₂，x₃)＝η(σ(x₁))是可由初始函数η以及σ，通过合成来定义的。)

然后定义乘法函数T(x，y)，为如下：

T(0，y)＝ζ()

T(n＋1，y)＝P(T(n，y)，y).

接下来我们定义指数函数E(x，y)，(通常0⁰被认为作未经定义的，但是因为原始递归函数必须是全函数，所以我们定义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)则已经超过10⁸⁴(因此，显著地超过了我们对宇宙中原子数量的估计值)。然而还有增长得快得多得原始递归函数。如我们看到的那样，E是通过慢增长函数σ来定义出来的，其使用了三个原始递归的应用：一个于加，一个于乘，然后就是指数运算。我们可以继续运用原始递归去构造一系列增长得难以想象地快的函数。让我们在定义超指数函数的系列中再多做一步，H(n，m) 为2次方的2次方的2次方…的m次方，像一座塔一样的n个2。H是原始递归的，因为它可以通过从E再多用一次原始递归，而定义出来：

H(0，y)＝y

H(n＋1，y)＝E(2，H(n，y))

因此H(2，2)＝2⁴＝16 H(3，3)＝2²56，多于10⁷⁷，与宇宙中原子的数目相当。如果你嫌这还不够大，你可以考虑H(4，4)。如果要用10进制来写这个数的话，前面的1后需接的0的数量，会比我们宇宙中粒子的数量都还多

3.1 Recursive Functions

原始递归函数的集是一个关于可计算函数的很庞大的类。实际上，它们可以被表征为在时间上可计算函数的集，这些函数是一些n的原始递归函数，而这里的n是输入的长度。例如，因为H(n，n)是一个原始递归函数，那么原始递归函数包含所有时间[H(n，n)](见下一节关于包含时间的计算复杂性(computational complexity)的讨论)。因此，原始递归函数包含所有这样的函数，其都是适宜于被任何，可以想象到的适合量度所计算的，甚至远远超过以上这些。

然而，原始递归函数并不包含所有原则上的可计算函数。为了看清这点，我们可以再次使用对角线法。我们可以系统地编码，所有元数为1的原始递归函数的定义，然后称这些为p₁，p₂，p₃ 等等。

然后我们可以构造一个图灵机去计算下面这些对角线式函数，D(n)＝pₙ(n)＋1

注意，D是全的，可计算的，从N到N的函数，但它不是原始递归的，为什么呢？为了构造矛盾，假设，D是原始递归的，那么，对于某个d ∈ N，D将等同于pd。但是这样一来就会出现，

pd(d)＝pd(d)＋1

而这是一个矛盾。因此，D不是原始递归的。

唉，上面的对角线论证，可以被考虑为对，所有为可计算函数的类的候选项的，全函数，都适用。对此问题来说，如果我们想要所有原则上可计算函数，而不只是实践上的，那么我们便需要引入一种无界的搜索操作(unbounded search operation)。这就是哥德尔将原始递归函数扩展到递归函数的做法。

Fori＝0 to ∞ do {

if f(i，x₁，. . .，xₖ)＝1，then output i {

所以，如果f(i，x₁，. . .，xₖ)＝1，并且对于所有j＜i f(j，x₁，. . .，xₖ)是已定义的，但不等于1，那么，μ[f](x₁，. . .，xₖ)＝i，否则μ[f](x₁，. . .，xₖ)就是未定义的。

哥德尔定义递归函数集为，在合成，原始递归，以及μ下的初始的原始递归函数，的闭包。有了这个定义，递归函数将非常精准地与，在lambda演算，克莱尼形式系统，马尔可夫算法，波斯特机与图灵机中的，部分可计算函数(partial computable function)的集相同。

1. Computational Complexity: Functions Computable in Practice

在二战中，图灵帮助设计并建造了一台专门的计算设备，被称为图灵炸弹(Bombe at Bletchley Park)。他运用这个东西去破解了德国的英格玛密码(“Enigma” code)，为盟军事业提供了极大的帮助(Hodges, 1992)。到了1960年代，计算机被广泛运用于了工业界与大学中。随着算法的发展，无数难题都得到了解决，一些数学家与科学家开始根据它们的效率，为这些算法分类，并寻找对特定问题的最优算法。而这是现代计算理论(theory of computation)的开端。

在这一节中我们开始处理复杂性，而不再是可计算性，而所有我们考虑的图灵机在这些输入上都将能够停机。我们将假定图灵机通过输出“1”表示接受，而非停机，那“0”则为拒绝，因此，我们从新定义被一个全图灵机接受的集合M，

L(M)＝n│M(n)＝1.

一个算法所需要的时间，取决于输入与运行该算法的机器。在复杂性理论中第一个关键的见解就是，对一个算法复杂性的，较好的衡量方法是，运用渐进于最坏情况复杂度(worst-case complexity)，其根据于输入大小n 。

对于一个输入ω，设n＝|ω| 为ω的长度。根据(Hartmanis, 1989)，我们说一个图灵机M的，运行所需时间为(runs in time) T(n)，如果，对于所有n长的ω，M(ω) 最多需要 T(n)步然后停机。这就被称为最坏情况复杂度，因为 T(n)必须不小于，在长度为n的任何输入上所需的时间。

对于任何一个函数，T：N → N，使得

TlME[T(n)]＝{A│A＝L(M)for some M thαt runs in time T(n)}.

Alan Cobham与Jack Edmonds确定了复杂度的P类，其为在一定多项式时间量(polynomial amount of time)中可识别的问题。这已是一个很好的数学工具，涵盖了可行问题的类，即所有这些问题的中等大小的实例都可以被识别出来，

P＝∪TlME[nⁱ]

i＝1，2，. . .

任何不在P中的问题，都是一定不可行的。而另一方面，有算法在P中的那些自然的问题，都倾向于，最终会有一个，被发现对这些问题实际可行的算法。

许多重要的包括在P中的计算复杂性类，都已被定义与研究，而少数则是NP，PSPACE，及EXPTlME。PSPACE包括那些，用多项式存储空间量(polynomial amount of memory space)可解的问题。EXPTlME是关于，在时间2⁽p(n))上可解的一些多项式p的集。

或许上面最有意思的类是NP：非确定性多项式时间(nondeterministic polynomial time)。其定义不是来自于一台真实的机器，而是一个数学抽象。一个非确定性图灵机N，其在每一步的两个可能行动中做出(猜测)一个选择，如果在输入ω上，这些选择的某个序列是可接受的，那么我们说N接受ω，以及我们说，N在输入ω上花了非确定的时间就是在这个导向接受的序列中所花的步数。非确定性机器不计所有其他的可能选择，而只计正确选择的单个序列。

NP时常被描绘为问题集S，其带有元素关系(membership)的简短证明。比如，假设我们被给定了关于m大小的自然数，α₁，. . .，αₘ及一个目标数t$$，的一个列表。这是一个子集和问题(Subset Sum problem)的实例：是否存在一个元素为m个数的子集，其和正好是t？在非确定性线性时间中，这个问题非常容易解决：对于每一个i，我们猜其是否取αᵢ。然后我们加上所有我们决定去取的数，如果上面的和等于t那么就接受。因此，这个非确定性时间是线性的，即，某个常值乘以输入的长度n。然而在此没有一种已知的(确定性)方法，可以在小于n的指数级时间内，去解决这个问题。

现在已经有了大量关于算法的研究，并且一些重要问题的复杂度也得到了很好的理解。尤其是，对问题间的还原进行了定义，并用其去比较两个问题的相对难度。直观地，我们说A是可还原(reducible)到B上的(A ≤ B) ，如果有一个简单的翻译τ，以一种保持元素关系的方式，将A的实例映射为B的实例，即，τ(ω) ∈ B ⇔ ω ∈ A。

值得注意的是，多数自然发生的计算问题，都被证明为，对上述的其中一个类中完全的(一个问题A，对一个复杂性类C是完全的，当，A是C中的一个成员，而C中的所有其他元素B不难于A，即，B ≤ A。两个对于同一个类而完全的问题拥有相等的复杂度。)

关于这种完全性现象的原因并没有得到充分的解释。一个可信的解释是，自然计算问题(natural computational problems)往往是通用的(译注：或作普遍的，下同)，在图灵的通用机的意义上。而关于某个既定复杂性类的，一个通用问题，可以模拟该类中任何其他问题。而NP类被如此广泛研究的原因则是，大量且重要的实际问题都是对于NP完全的，包括子集和问题。而其中没一个被已知，存在一个算法，其可以快于指数级的时间去解决它们，尽管一些NP完全问题允许关于它们的近似可行解。

关于计算复杂性的大量的问题都还是开放的。我们知道，严格地说，更多的计算资源(computational resources)，可使得我们解决，严格上更难的问题，例如TlME[n]真包含于TlME[n¹.01]中，相似地，对于SPACE ，以及其他量度来说同样如此。然而，在不同计算资源间的权衡上，我们的理解仍然十分贫乏。显然，P被包含于NP中。进一步，NP被包含在PSPACE中，因为在PSPACE中，我们可以系统性地尝试NP计算的每一个分支，对连续的分支再利用空间，并且接受它，当且仅当这些分支中的任何一个导向了接受。PSPACE被包含在EXPTlME中，因为，当一个PSPACE机要花超过指数级的时间时，那么它就确切地重复了一些配置，所以它也一定是在无限循环。以下是关于上面这些类的已知关系

P ⊆ NP ⊆ PSPACE ⊆ EXPTlME

然而，尽管看上去很清楚地，P真包含于NP，而NP真包含于PSPACE，PSPACE也真包含于EXPTIME，但其中任何这些类的不等关系都没有得到过证明。实际上，甚至对于P是否不同于PSPACE，或者NP是否不同于EXPTIME，我们都是不知道的。从上面可知，真包含关系只有，P真包含于EXPTIME。余下的问题，涉及到不同计算资源的相对效力，而这是个计算理论中的基础性的未解难题。

关于计算复杂性有一个广泛的理论，本条目只简单描述了这一领域，将其置于在了，什么是原则上与实践上可计算的，这个问题的语境下。对于那些有志于学习更多关于复杂性的读者有很多非常不错的著作，比如[Papadimitriou, 1994]，与[Arora and Barak, 2009]，以及同样有条目Computational Complexity Theory。

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。