Ackermann函数

Ackermann函数的历史

1920年代后期,数学家大卫·希尔伯特的学生Gabriel Sudan和威廉·阿克曼,当时正研究计算的基础。Sudan发明了一个递归却非原始递归的Sudan函数。1928年,阿克曼又独立想出了另一个递归却非原始递归的函数。
他最初的念头是一个三个变量的函数A(m,n,p),使用康威链式箭号表示法是m→n→p。阿克曼证明了它是递归函数。希尔伯特在On the Infinite猜想这个函数不是原始递归函数。阿克曼在On Hilbert’s Construction of the Real Numbers证明了这点。
后来Rózsa Péter和拉斐尔·米切尔·罗宾逊定义了一个类似的函数,但只用两个变量。

Ackermann函数的递归定义

Ackermann函数的意义

似乎直接看定义的话看不出这个函数有多“恐怖”。
Ackermann函数可以看成关于n的一个函数序列,其中第0个函数返回n+1,而第m个函数则是将第m-1个函数对1迭代n+1遍。
如果我们定住其中一个变量(比如m),试着推一下通项公式:
Ackermann(0,n)=n+1
Ackermann(1,n)=n+2
Ackermann(2,n)=2*n+3
Ackermann(3,n)=2^(n+3)-3
Ackermann(4,n)=2^2^2^……^2-3,乘幂中共有n+3个2。
当m≥4,Ackermann函数的增长快得惊人。
Ackermann(4,0)=13,
Ackermann(4,1)=65533,
Ackermann(4,2)=2^65536-3有19729位,
而Ackermann(4,3)则即使是位数也不易估计。
Ackermann(5,0)=65533,
Ackermann(5,1)=Ackermann(4,65533)……

可以发现,Ackermann函数的增长异常恐怖,只要我们数几个数(1,2,3,4,5)它就已经爆炸了…几乎瞬间超出了宇宙中的原子数,这,就是迭代的威力
当然,万事万物都有它的反面。我是说,如果Ackermann函数增长得太快,那么什么是增长地比较慢的呢?
Ackermann^-1(x)!
(我特意用了中文感叹号来表示这不是阶乘的意思)
实际上,在带路径压缩的并查集(DisjointSet)中,这个数据结构的时间复杂度中就引入了阿克曼函数的反函数(更准确地说,单次操作的均摊成本是O(alpha(n)),其中n为元素个数,alpha()是阿克曼函数的反函数,这个数字在本世纪应该都不会达到5,在渐近意义上是要优于O(log2(n))对数复杂度的)

Ackermann函数的递归计算中间过程输出

用Python弄了个递归计算Ackermann函数中间过程的函数(以数学可读的方式)
Code:(Python3.6.7)

def Ackermann(expr):
print("=", expr.replace("(", " A(")) # 以人可读的方式输出
l = expr.rfind("(") # 找到左括号
r = expr.find(")") # 找到右括号
if l == -1 or r == -1: # 没找到说明当前表达式即是答案,递归终止
return
args = expr[l : r + 1] # 若找到
mid = args.find(",") # 由','隔开的两边分别读为m和n
m = int(args[1:mid])
n = int(args[mid + 1 : r - l])
if m == 0: # Ackermann函数的计算方式
new = str(n + 1) # 并将之格式化以继续递归
elif n == 0:
new = "(" + str(m - 1) + ",1)"
else:
new = "(" + str(m - 1) + ",(" + str(m) + "," + str(n - 1) + "))"
Ackermann(expr.replace(args, new)) # 每次替换后继续计算

while 1:
m = input("input m:") # 输入m,n
n = input("input n:")
expr = "(" + m + "," + n + ")"
Ackermann(expr) # 实测当m,n稍微大一些(大于5)的时候递归层数就过多了

测试:

input m:2
input n:1
= A(2,1)
= A(1, A(2,0))
= A(1, A(1,1))
= A(1, A(0, A(1,0)))
= A(1, A(0, A(0,1)))
= A(1, A(0,2))
= A(1,3)
= A(0, A(1,2))
= A(0, A(0, A(1,1)))
= A(0, A(0, A(0, A(1,0))))
= A(0, A(0, A(0, A(0,1))))
= A(0, A(0, A(0,2)))
= A(0, A(0,3))
= A(0,4)
= 5

发表评论

电子邮件地址不会被公开。 必填项已用*标注