Ackermann-Funktion

Ackermann-Funktion
f (0, n) = n + 1
f (m, 0) = f (m − 1, 1)
f (m, n) = f (m − 1, f (m, n − 1))
def ack(m, n):
if m == 0:
return n + 1
elif n == 0:
return ack(m − 1, 1)
else:
return ack(m − 1, ack(m, n − 1))
A(m, n)
n=0 n=1
n=2
n=3
n=4
n=5
m=0
1
2
3
4
5
6
m=1
2
3
4
5
6
7
m=2
3
5
7
9
11
13
m=3
5
13
29
61
65536
13 65533 265536 − 3 22
m=4
m=5
m=6
125
65536
22
−3 2
253
265536
22
−3 2
−3
65533
2...
22
2
(65536mal) − 3
A(1, n) = n + 2
A(2, n) = 2n + 3
A(3, n) = 2n+3 − 3
A(4, 2) hat schon 19729 Stellen.
Die Zahl ist größer als die (vermutete) Anzahl der Atome im Weltraum.
Genau die primitiv-rekursiven Funktionen können mit Additionen, Zuweisungen und loop-Schleifen
programmiert werden. Für die Ackermann-Funktion (1928) trifft das nicht zu.
Sie wächst schneller als jede primitiv-rekursive Funktion.
c Roolfs
1
Ackermann-Funktion anschaulich
f (0, n) = n + 1
f (m, 0) = f (m − 1, 1)
f (m, n) = f (m − 1, f (m, n − 1))
m/n
f (m, n − 1)
0
1
2 n−1 n
5
0
1
2
3
4
5
6
7
8
9
10
11
12
13
1
2
3
4
5
6
7
8
9
10
11
12
13
14
m−1
3
5
7
9
11
13
15
17
19
21
23
bc
25
27
m
5
f (m − 1, f (m, n − 1))
bc
bc
f (m, n − 1) f (m, n)
5
c Roolfs
2

Download Report