阿克曼函数

一个以显式给出的非原始递归的递归全函数。

部分递归函数中有定义域不全的函数，而原始递归函数都是全函数。一个自然的问题是：原始递归函数是否就是全体递归全函数?1942年阿克曼(Ackermann)用一个例子对上述问题作了否定回答。这个例子后来就被称为阿克曼函数，其定义如下：

容易看出A(x，y)是个全函数。阿克曼证明A(x，y)是递归的，但不是原始递归的。证明后一半(非原始递归)，主要是证明A(x，y)比任何一个原始递归函数都增长得更快。严格地讲，是证明：对于任一元原始递归函数f(x)，存在常数C使f(x)＜A(C，x)。在这个基础上就容易看出A(x，y)不是原始递归函数了。因为若A(x，y)原始递归，则A(x，x)也原始递归，从而存在C使A(x，x)＜A(C，x)。取x=C，矛盾。阿克曼函数的定义方法也是一种“递归”，阿克曼的结果表明，这种递归不能还原为原始递归和复合运算。