Die Ackermann-Funktion ist ein prominentes Beispiel für eine rekursive Funktion, die jetzt — und noch die nächsten Jahrzehnte — Informatiker im Studium beschäftigt.
Sie ist nach F. Wilhelm Ackermann (1886-1962) benannt. Viele Funktionen der mathematischen Praxis sind primitiv rekursiv, und David Hilbert stellte 1926 die Frage, ob alle Funktionen, deren Argumente und Werte natürliche Zahlen sind, primitiv rekursiv sind. Die Ackermann-Funktion steigt sehr stark an und ist für Theoretiker ein Beispiel dafür, dass es berechenbare Funktionen gibt, die aber nicht primitiv rekursiv sind. Im Jahre 1928 zeigte Ackermann dies an einem Beispiel: der Ackermann-Funktion.6 Sie wächst stärker als es Substitution und Rekursion ermöglichen und nur für kleine Argumente lassen sich die Funktionswerte noch ohne Rekursion berechnen. Darin bestand auch die Beweisidee von Ackermann, eine Funktion zu definieren, die schneller wächst als alle primitiv rekursiven Funktionen. Wir wollen hier nicht die originale Version von Ackermann benutzen, die durch die Funktionalgleichung
f(n‘, x‘, y‘) = f(n, f(n‘, x, y), x)
ausgedrückt wird, sondern die vereinfachte Variante von Hans Hermes. Wir wollen die Version von Hermes aber fortan auch Ackermann-Funktion nennen, da sie direkt aus dem Original gewonnen wird. Für die oben angegebene Funktion muss in der Abhandlung von Ackermann nachgeblättert werden, um den Nachweis des Nicht-primitiv-rekursiv-Seins zu finden.
Die neue Ackermann-Funktion ist eine Abbildung von zwei ganzen Zahlen auf eine ganze Zahl a(n,m). Sie ist mathematisch durch folgende Gesetzmäßigkeit definiert:
a(0,m) = m + 1
a(n,0) = a(n – 1, 1)
a(n,m) = a(n – 1, a(n, m – 1))
Die Ackermann-Funktion ist dafür berühmt, die Rechenkapazität ganz schnell zu erschöpfen. Sehen wir uns die Implementierung in Java an und testen wir das Programm mit ein paar Werten.
class Ackermann
{
public static long ackermann( long n, long m )
{
if ( n == 0 )
return m + 1;
else
if ( m == 0 )
return ackermann( n - 1, 1 );
else
return ackermann( n - 1, ackermann(n, m - 1) );
}
public static void main( String args[] )
{
int x = 2,
y = 2;
System.out.println( "ackermann(" + x + "," + y + ")=" + ackermann(x,y) );
}
}
Für den Aufruf ackermann(1, 2) veranschaulicht die folgende Ausgabe die rekursive Eigenschaft der Ackermann-Funktion. Die Stufen der Rekursion sind durch Einrückungen deutlich gemacht:
a(1,2):
a(0,a(1,1)):
a(0,a(1,0)):
a(1,0):
a(0,1)=2
a(1,0)=2
a(0,2)=3
a(0,a(1,0))=3
a(0,3)=4
a(0,a(1,1))=4
a(1,2)=4
Bei festen Zahlen lässt sich der Wert der Ackermann-Funktion direkt angeben.
a(1,n) = n + 2
a(2,n) = 2n + 3
a(3,n) = 2n+3 – 3
Für große Zahlen übersteigt die Funktion aber schnell alle Berechnungsmöglichkeiten. Zum Vergleich: Die Ackermannfunktion berechnet beim Zahlenpaar (4,7) etwa 0,2*10^20. Unter der Definition a(0,y) = y+1; a(x+1) = a(x,1); a(x+1,y+1) = a(x, (a+1),y)) ergibt sie die folgende große Tabelle.
|
A(x,y) |
y = 0 |
y = 1 |
y = 2 |
y = 3 |
y = 4 |
y = 5 |
|---|---|---|---|---|---|---|
|
x = 0 |
1 |
2 |
3 |
4 |
5 |
6 |
|
x = 1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
x = 2 |
3 |
5 |
7 |
9 |
11 |
13 |
|
x = 3 |
5 |
13 |
29 |
61 |
125 |
253 |
|
x = 4 |
13 |
65533 |
265536-3 |
2265536-3 |
a(3, 2265536-3) |
a(3,a(4,4)) |
|
x = 5 |
65533 |
a(4,65533) |
a(4, a(4,65533)) |
a(4,a(5,2)) |
a(4,a(5,3)) |
a(4,a(5,4)) |
|
x = 6 |
a(4,65533) |
a(5, a(4,65533)) |
a(5,a(6,1)) |
a(5,a(6,2)) |
a(5,a(6,3)) |
a(5,a(6,4)) |
Ackermann-Funktion für einige Werte
Die Ackermann Funktion wächst, obwohl sie Turing-berechenbar ist, schneller als alle primitiv rekursiven Funktionen. Normale mathematische Notationen versagen beim Schreiben dieser großen Zahlen und eine andere Möglichkeit muss her um große Zahlen zu definieren. Schauen wir uns doch erst einmal an, woher die großen Zahlen überhaupt kommen. Dazu eine alternative Definition, nach der ersten Zahle entwickelt:
a(0,n) = n + 1
a(1,n) = 2 + (n + 3) – 3
a(2,n) = 2 * (n + 3) – 3
a(3,n) = 2 ^ (n + 3) – 3
a(4,n) = 2 ^ 2 ^ … ^ 2 – 3 (wobei die Potenz (n+3)-mal erhoben wird)
Schon bei der Definition von a(4,n) tritt n mal eine Zweierpotenz auf. Mit der herkömmlichen Schreibweise unhandelbar. Glücklicherweise haben sich berühmte Männer mit neuen Notationen einen Namen gemacht, unter ihnen der nimmer müde werdende Donald E. Knuth. Er schuf 1976 die Up-Arrow-Notation (auf deutsch etwa Nach-oben-Pfeil-Notation – wir bleiben an dieser Stelle aber englisch). Die Schreibweise wird am besten an der Motivation, die Multiplikation einzuführen, verdeutlicht. Addieren wir n mal den Summanden m, so entspricht dies einer Multiplikation vom m mit der Anzahl n (m + m + … + m = m * n). Bilden wir die Potenz einer Zahl, multiplieren wir n mal m, so schreibt sich dies m ^ n = m m … m = mn. Führen wir dies weiter. Was kommt mach dem n-maligen Produkt? Es kommt danach die n-te Potenz (in Zeichen m^^n, daher zwei mal das Zeichen ^^). Fassen wir bisheriges mit einigen Beispielen zusammen:
2^2 = 2*2 = 4
2^3 = 2*2*2 = 8
2^4 = 2*2*2*2 = 16
3^2 = 3*3 = 9
3^3 = 3*3*3 = 27
3^4 = 3*3*3*3 = 81
4^2 = 4*4 = 16
4^3 = 4*4*4 = 64
4^4 = 4*4*4*4 = 256
2^^2 = 2^2 = 4
2^^3 = 2^2^2 = 2^4 = 16
2^^4 = 2^2^2^2 = 2^16 = 65536
3^^2 = 3^3 = 27
3^^3 = 3^3^3 = 3^27 = 7625597484987
3^^4 = 3^3^3^3 = 3^3^27 = 3^7625597484987
2^^^2 = 2^^2 = 4
2^^^3 = 2^^2^^2 = 2^^4 = 65536
2^^^4 = 2^^2^^2^^2 = 2^^65536 = 2^2^…^2 (65536 mal)
3^^^2 = 3^^3 = 7625597484987
3^^^3 = 3^^3^^3 = 3^^7625597484987 = 3^3^…^3 (7625597484987 mal)
3^^^4 = 3^^3^^3^^3 = 3^^3^^7625597484987 = 3^3^…^3 (3^^7625597484987 mal)
2^^^^2 = 2^^^2 = 4
2^^^^3 = 2^^^2^^^2 = 2^^^4 = 2^2^…^2 (65536 mal)
2^^^^4 = 2^^^2^^^2^^^2 = 2^^^2^2^…^2 (65536 mal)
3^^^^2 = 3^^^3 = 3^3^…^3 (7625597484987 mal)
3^^^^3 = 3^^^3^^^3 = 3^^^3^3^…^3 (7625597484987mal)
= 3^^3^3^…^3 (3^3^…^3 (7625597484987 mal) mal)
Nun endlich lassen sich die großen Zahlen mit kleinen Formeln schreiben. So für die ersten fünf Elemente:
a(1, n) = 2 + (n + 3) – 3
a(2, n) = 2 (n + 3) – 3
a(3, n) = 2 ^ (n + 3) – 3
a(4, n) = 2 ^^ (n + 3) – 3
a(5, n) = 2 ^^^ (n + 3) – 3
John H. Conway geht noch einen Schritt weiter, denn auch die Up-Arrow-Schreibweise kann die Formel für a(m,n) nicht ohne den Zusatz »^…^ und dass n-2 mal« lösen. Conway schafft dies mit seiner Chained-Arrow Notation (zu deutsch etwa Ketten-Pfeil Notation, aber wir bleiben wieder beim englischen Begriff). Conway führt für »^…^« die Schreiweise
a -> b -> c = a ^^…^^ b
ein, wobei c die Anzahl der Potenzen beschreibt. Nun endlich vereinfacht sich auch der die Ackermann-Funktion. Es folgt:
a(m, n) = 2 -> (n + 3) -> (m – 2) – 3