SEP：可计算性与复杂性（二） (5-3)

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 。

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。