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

在其中，每个ωᵢ为，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的数量，会比我们宇宙中粒子的数量都还多

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