Die Ackermannfunktion ist eine 1926 von Wilhelm Ackermann gefundene, extrem schnell wachsende mathematische Funktion, mit deren Hilfe in der theoretischen Informatik Grenzen von Computer- und Berechnungsmodellen aufgezeigt werden können. Heute gibt es eine ganze Reihe von Funktionen, die als Ackermannfunktion bezeichnet werden. Diese weisen alle ein ähnliches Bildungsgesetz wie die ursprüngliche Ackermannfunktion auf und haben auch ein ähnliches Wachstumsverhalten.

Entstehungsgeschichte

---

1926 vermutete David Hilbert, dass jede berechenbare Funktion primitiv-rekursiv sei. Vereinfacht bedeutet dies, dass sich jede durch einen Computer berechenbare Funktion aus einigen wenigen, sehr einfachen Regeln zusammensetzen lässt und dass sich die Dauer der Berechnung im Voraus abschätzen lässt. Dies trifft auf nahezu alle in der Praxis vorkommenden Funktionen zu.

Ebenfalls 1926 konstruierte Ackermann eine Funktion, die diese Vermutung widerlegt, und veröffentlichte sie 1928. Diese Funktion wird heute, ihm zu Ehren, Ackermannfunktion, genannt. Die Ackermannfunktion kann also von einem Computer in endlicher Zeit ausgewertet werden, ist aber nicht primitiv-rekursiv.

1955 konstruierte Rózsa Péter eine vereinfachte Version, die die gleichen Eigenschaften besitzt. Diese Funktion, gelegentlich auch als Ackermann-Péter-Funktion bezeichnet, wird heute vorwiegend benutzt.

Idee

---

Man betrachtet die Folge $a+b$, $a\backslash cdot\; b$, $a^b$, $\backslash ldots$ Hierbei wird bei jedem Folgeglied die Operation des vorigen Folgeglieds $b$ mal auf $a$ angewandt, also $a\backslash cdot\; b$ ist gerade $a+a+\backslash ldots\; +a$, wobei die Variable $a$ $b$-mal vorkommt und so weiter. Die Idee hinter der Ackermannfunktion ist es, diese Folge als Funktion aufzufassen.

Beispiel: Setzt man in obiger Folge $a=2$ und $b=4$, so erhält man die Folge: 6, 8, 16, 65536, $2^\{2^\{.^\{.^\{.^\{2\}\}\}\}\}$ (mit 65536 Zweien), ..., die man auch die Ackermannfunktion zu $a=2$ und $b=4$ nennt. Die letzte aufgeführte Zahl ist bereits wesentlich größer als die geschätzte Anzahl der Atome im gesamten Weltall.

Die Ackermannfunktion, notiert als $\backslash phi$, ist also eine Funktion, die die folgenden Gleichungen erfüllt:

$\backslash phi(a,\; b,\; 0)\; =\; a+b\backslash ,$

$\backslash phi(a,\; b,\; 1)\; =\; a\; \backslash cdot\; b$

$\backslash phi(a,\; b,\; 2)\; =\; a^b\backslash ,$

$\backslash ldots$

Ab der vierten Zeile können die Funktionswerte nicht mehr mit herkömmlichen Operatoren formuliert werden; man braucht erweiterte Notationen, wie beispielsweise den Hyper-Operator.

Definition und Varianten

---

Die Ackermannfunktion definiert man üblicherweise rekursiv, d. h., man macht für einige Anfangswerte explizite Angaben und gibt eine Anleitung (das Rekursionsschema), wie man weitere Funktionswerte aus den bereits berechneten erhält.

Definition von Ackermann

Ackermann selbst definierte die Funktion auf recht umständliche Weise, gab aber kurz darauf die folgende äquivalente Definition an.

$\backslash phi(a,\; b,\; 0)=a+b\backslash ,$

$\backslash phi(a,\; 0,\; n+1)=\backslash psi(a,\; n)\backslash ,$

$\backslash phi(a,\; b+1,\; n+1)=\backslash phi(a,\; \backslash phi(a,\; b,\; n+1),\; n)\backslash ,$

Dabei ist $\backslash psi(a,\; n)$ eine weitere Funktion, die Ackermann nicht weiter beschrieb. (Sie liefert die Startwerte $a+0$, $a\backslash cdot\; 0$, $a^0$, $\backslash ldots$.)

Beispiele:

• Möchte man $\backslash phi(4,\; 3,\; 0)$ berechnen, so kann man die erste Zeile der Definition anwenden und erhält direkt: $\backslash phi(4,\; 3,\; 0)\; =\; 4+3\; =\; 7$.
• Möchte man $\backslash phi(4,\; 0,\; 2)$ berechnen, so kann man die zweite Zeile der Definition anwenden und erhält ebenfalls direkt: $\backslash phi(4,\; 0,\; 2)\; =\; \backslash psi(4,\; 1)\; =\; 4^0\; =\; 1$. Man beachte, dass in diesem Fall $n$ den Wert 1 hat, da auf der linken Seite der Definition $n+1$ steht.
• Komplizierter wird es, wenn weder das zweite, noch das dritte Argument 0 ist. Beispielsweise möchte man $\backslash phi(4,\; 1,\; 2)$ berechnen. Da sich die ersten beiden Zeilen der Definition nicht anwenden lassen, muss man die dritte verwenden. Damit erhält man: $\backslash phi(4,\; 1,\; 2)=\backslash phi(4,\; \backslash phi(4,\; 0,\; 2),\; 1)$. $\backslash phi(4,\; 0,\; 2)$ wurde aber gerade im vorigen Beispiel berechnet. Setzt man dies ein, so erhält man $\backslash phi(4,\; 1,\; 2)=\backslash phi(4,\; 1,\; 1)$. Jetzt kann man wieder die dritte Zeile anwenden, dann nochmal die zweite und zuletzt die erste Zeile der Definition. Alles zusammen ergibt in diesem Fall:

{| $\backslash phi(4,\; 1,\; 2)\backslash ,$ $=\backslash phi(4,\; \backslash phi(4,\; 0,\; 2),\; 1)\backslash ,$ $=\backslash phi(4,\; 1,\; 1)\backslash ,$ $=\backslash phi(4,\; \backslash phi(4,\; 0,\; 1),\; 0)\backslash ,$ $=\backslash phi(4,\; 0,\; 0)\backslash ,$ $=4\backslash ,$

Wenn man vom Wachstum der Ackermannfunktion spricht, meint man oftmals die Funktion $f(n)\; :=\; \backslash phi(n,\; n,\; n)$.

Definition von Péter

Rózsa Péter definierte 1955 eine einfachere Version der Ackermannfunktion, die nur zwei Parameter besitzt und zudem ohne die Hilfsfunktion $\backslash psi$ auskommt:

$\backslash textrm\{a\}(0,\; m)\; =\; m+1\backslash ,$

$\backslash textrm\{a\}(n+1,\; 0)\; =\; \backslash textrm\{a\}(n,\; 1)\backslash ,$

$\backslash textrm\{a\}(n+1,\; m+1)\; =\; \backslash textrm\{a\}(n,\; \backslash textrm\{a\}(n+1,\; m))\backslash ,$

Auch hier meint man im Zusammenhang mit Wachstumsuntersuchungen oftmals die Funktion $f(n)\; :=\; \backslash textrm\{a\}(n,\; n)$, wenn man von der Ackermannfunktion spricht.

Aus dieser Definition ist nicht sofort ersichtlich, dass die Funktion für alle nicht negativen, ganzzahligen $n$ und $m$ definiert ist. Das ergibt sich jedoch daraus, dass in jedem Schritt, entweder $m$ verringert oder aber $m$ erhöht und $n$ verringert wird. Jedesmal, wenn $m$ Null erreicht, wird $n$ verringert, also muss auch $n$ irgendwann Null erreichen, und dann liefert die erste Zeile der Definition den Funktionswert. Zu beachten ist allerdings, dass es bei einer Verringerung von $m$ keine obere Schranke für das Wachstum von $n$ in den folgenden Funktionsaufrufen gibt.

Bedeutung in der theoretischen Informatik

---

Wie eingangs schon erwähnt, erfand Ackermann diese Funktion als Beispiel einer Funktion, die nicht primitiv-rekursiv ist, aber berechenbar. Dies ist auch heute noch das wichtigste Anwendungsgebiet der Ackermannfunktion.

Auf der Suche nach den Grenzen von Computern stößt man sehr schnell auf den Begriff der berechenbaren Funktionen. Das sind all die Funktionen, für deren Auswertung man einen Algorithmus angeben kann, also alle Funktionen, die ein Computer berechnen kann. Diese Definition stellt einen sehr schnell vor ein Problem, wenn man von einer konkreten Funktion entscheiden möchte, ob sie berechenbar ist. Findet man einen Algorithmus, der die Funktion berechnet, so ist sie offensichtlich berechenbar. Andernfalls ist ungewiss, ob die Funktion wirklich nicht berechenbar ist oder ob es zwar einen Algorithmus gibt, man ihn aber nicht gefunden hat.

Aus diesem Grund sucht man nach alternativen Definitionen, mit denen man einen solchen Nachweis einfacher führen kann. Ein erster Ansatz hierfür waren die primitiv-rekursiven Funktionen. Dies sind Funktionen, die sich durch einige wenige Regeln aus sehr einfachen Funktionen zusammensetzen lassen.

Einige Zeit vermutete man, dass alle berechenbaren Funktionen primitiv-rekursiv sind, mit den primitiv-rekursiven Funktionen also ein Werkzeug zur Lösung des oben geschilderten Problems gefunden sei. Diese Hoffnung zerstörte jedoch die Ackermannfunktion, von der man nachweisen kann, dass sie berechenbar, aber nicht primitiv-rekursiv ist. (Siehe nachfolgenden Expertenabschnitt.)

Anmerkung: Inzwischen weiß man, dass man aus den primitiv-rekursiven Funktionen die berechenbaren erhält, wenn man noch eine weitere Konstruktionsregel, die sogenannte µ-Rekursion, zulässt.

Beweis

Der Beweis, dass die Ackermannfunktion berechenbar ist, aber nicht primitiv-rekursiv, nutzt im Wesentlichen aus, dass die Ackermannfunktion stärker wächst als jede primitiv-rekursive Funktion.

Anwendungen

---

Für die Ackermannfunktion gibt es nur sehr wenige Anwendungen. Die zwei wichtigsten sind Benchmarktests für rekursive Aufrufe in Programmiersprachen und Laufzeitabschätzungen der gewichteten Vereinigung und Pfadkompression bei der Union-Find-Struktur.

Benchmark für rekursive Aufrufe

Bei der Einführung von neuen Programmiersprachen, Compilern und Computern möchte man deren Leistungsfähigkeit untersuchen. Dazu werden u. a. mittels Benchmarking durch spezielle Programme festgelegte Eigenschaften überprüft.

In diesem Zusammenhang wird die Ackermannfunktion gerne als Benchmark zur Überprüfung von rekursiven Prozedur-Aufrufen benutzt, da ein Programm zur Berechnung der Ackermannfunktion im Wesentlichen nur aus solchen Prozeduraufrufen besteht. In der Definition von Péter wird ja nur $a(0,\; m)$ direkt berechnet. Die Schwierigkeit bei der Berechnung der Funktionswerte sind also nicht allein deren Größe, sondern die tiefe Verschachtelung der Funktionsaufrufe, die leicht zu einem Stapelüberlauf (engl. Stack Overflow) führt, also dazu, dass dem System der Speicher ausgeht.

Diese Idee geht zurück auf Yngve Sundblad, der 1971 die Funktion $f(n):=a(3,\; n)$ benutzte, um diverse Programmiersprachen zu vergleichen. Um $a(3,\; n)$ zu berechnen, werden $a(3,\; n)+12^n-2$ Aufrufe getätigt.

Sundblad testete unter anderem, wie groß $n$ gewählt werden kann, damit der Computer noch in der Lage ist, diese Zahl zu berechnen. Damals erreichte er $n=1$. Zum Vergleich hierzu: Mit Java 1.4.2, mit den Standardspeichereinstellungen, erreicht man heutzutage $n=13$.

Im Laufe der Berechnung werden viele identische Aufrufe mehrfach ausgerechnet. Ein intelligenter Compiler kann dies ausnutzen und die Ergebnisse zwischenspeichern, um solche Aufrufe nur einmal durchführen zu müssen. Damit waren schon 1971 Aufrufe bis $n=20$ durchführbar. Einen bedeutenden Zeitvorteil erhält man auch, wenn man $a(1,\; n)$ direkt berechnet, statt es rekursiv zu $a(1,\; a(1,\; a(1,\; \backslash dots\; a(1,\; 0)\backslash dots)))$ zu expandieren. Die direkte Berechnung von $a(1,\; n)$ erfordert lineare Zeit in $n$. Die Berechnung von $a(2,\; n)$ erfordert quadratische Zeit, denn sie führt zu $O(n)$ (also $c\backslash cdot\; n$ für eine Konstante $c$) verschachtelten Aufrufen von $a(1,\; i)$ für verschiedene $i$. Die Berechnung von $a(3,\; n)$ erfordert schließlich eine zu $4^\{n+1\}$ proportionale Zeit ($O(4^\{n+1\})$; zur Erklärung der Groß-O-Notation siehe Landau-Symbole).

Laufzeitabschätzungen mit der Umkehrfunktion

Da die Funktion $f(n):\; =\; a(n,\; n)$ sehr schnell wächst, wächst ihre Umkehrfunktion $f^\{-1\}$ sehr langsam. Sie ist für jede praktisch vorstellbare Eingabegröße kleiner als 5, weil der Funktionswert $f(4)=a(4,\; 4)$ größer als die Anzahl der Atome im Universum ist, wie die Berechnung von $a(4,\; 3)$ weiter unten zeigt. In der praktischen Analyse von Algorithmen kann sie also als konstant betrachtet werden.

Diese Umkehrfunktion taucht in der Laufzeitanalyse bestimmter Algorithmen auf, zum Beispiel beim Union-Find-Problem und in Chazelles Algorithmus für minimale Spannbäume. In diesem und anderen Zusammenhängen wird die ursprüngliche Ackermannfunktion oft durch Weglassen additiver Konstanten, oder anderer Modifikationen, leicht umdefiniert zu einer Funktion mit ähnlichem asymptotischen Verhalten. Diese modifizierten Funktionen sind nicht äquivalent zur Ackermannfunktion, aber nach den Maßstäben der Laufzeitanalyse können sie als äquivalent betrachtet werden.

Implementierung

---

Die rekursive Implementierung der Ackermannfunktion (hier in Pseudo-Code) entspricht direkt der Definition:

function ack(n, m) if n = 0 return m + 1 else if m = 0 return ack(n - 1, 1) else return ack(n - 1, ack(n, m - 1))

Etwas effizienter ist die folgende, teilweise iterative Implementierung:

function ack(n, m) while n ≠ 0 if m = 0 m := 1 else m := ack(n, m - 1) n := n - 1 return m + 1

Noch effizientere Implementierungen verwenden Arrays zur Zwischenspeicherung bereits berechneter Werte, siehe auch Dynamische Programmierung.

In Haskell, einer funktionalen Programmiersprache, spiegelt die Implementierung direkt die Definition wider:

ack 0 m = m+1 ack (n+1) 0 = ack n 1 ack (n+1) (m+1) = ack n (ack (n+1) m)

In Prolog sieht die Implementierung so aus:

ackermann(0,X,Y) :- X >= 0, !, Y is X + 1. ackermann(X,0,Z) :- X > 0, !, X1 is X - 1, ackermann(X1,1,Z). ackermann(X,Y,Z) :- X > 0, Y > 0, X1 is X-1, Y1 is Y - 1, ackermann(X,Y1,W), ackermann(X1,W,Z).

Wertetabelle

---

Die folgende Tabelle zeigt einige Funktionswerte für kleine Werte von $n$ und $m$. Die nicht vollständig ausgerechneten Werte sind zu groß, um sie dezimal darzustellen.

{| Werte von $a(n,\; m)$

! n \ m 0 1 2 3 4 $m$

---

- 0 1 2 3 4 5 $m+1$

---

- 1 2 3 4 5 6 $m+2$

---

- 2 3 5 7 9 11 $2m+3$

---

- 3 5 13 29 61 125 $8\backslash cdot\; 2^m-3$

---

- 4 13 65533 $2^\{65536\}-3\; \backslash approx\; 2\; \backslash cdot\; 10^\{19728\}$ ¹ $a(3,\; 2^\{65536\}-3)$ $a(3,\; a(4,\; 3))$ $2^\{2^\{\backslash dots^2\}\}-3$ ($m+3$ Terme)

---

- 5 65533 $a(4,\; 65533)$ $a(4,\; a(5,\; 1))$ $a(4,\; a(5,\; 2))$ $a(4,\; a(5,\; 3))$

---

- 6 $a(5,\; 1)$ $a(5,\; a(5,\; 1))$ $a(5,\; a(6,\; 1))$ $a(5,\; a(6,\; 2))$ $a(5,\; a(6,\; 3))$

¹eine Zahl mit 19729 Dezimalstellen

Trotz der unvorstellbar großen Zahlen, die schon in dieser Tabelle auftauchen, wurden rekursive Verfahren definiert, die noch schneller wachsende Werte liefern, so zum Beispiel Grahams Zahl.

Genauere Betrachtung

---

Anhand der Wertetabelle lässt sich ein Schema zur Berechnung der Funktionswerte herleiten, das leichter zu verstehen ist als die formale rekursive Definition. Intuitiv ist die erste Zeile der Wertetabelle (genauer: die Werte von $a(0,\; y)$) einfach eine Liste aller natürlichen Zahlen, und die auf das Argument $y$ angewandte mathematische Operation ist die Addition einer 1 zu $y$. Alle folgenden Zeilen enthalten einfach Anweisungen, in dieser Zeile einen Wert zu suchen. Im Falle der Zeile $x=1$ vereinfacht sich diese Anweisung dazu, den Wert $a(0,\; y+1)$ in der Zeile $x=0$ zu suchen, aber diese Vereinfachung ist schon etwas schwieriger herzuleiten – zum Beispiel: a(1, 2) = a(0, a(1,1)) = a(0, a(0, a(1,0))) = a(0, a(0, 2)) = a(0, 3) = 4

Wir betrachten nun einen komplexeren Fall, nämlich $a(4,\; 3)$, den ersten Funktionswert, der so groß ist, dass er praktisch nicht dezimal aufgeschrieben werden kann.

a(4, 3) = a(3, a(4, 2)) = a(3, a(3, a(4, 1))) = a(3, a(3, a(3, a(4, 0)))) = a(3, a(3, a(3, a(3, 1)))) = a(3, a(3, a(3, a(2, a(3, 0))))) = a(3, a(3, a(3, a(2, a(2, 1))))) = a(3, a(3, a(3, a(2, a(1, a(2, 0)))))) = a(3, a(3, a(3, a(2, a(1, a(1, 1)))))) = a(3, a(3, a(3, a(2, a(1, a(0, a(1, 0))))))) = a(3, a(3, a(3, a(2, a(1, a(0, a(0, 1))))))) = a(3, a(3, a(3, a(2, a(1, a(0, 2)))))) = a(3, a(3, a(3, a(2, a(1, 3))))) = a(3, a(3, a(3, a(2, a(0, a(1, 2)))))) = a(3, a(3, a(3, a(2, a(0, a(0, a(1, 1))))))) = a(3, a(3, a(3, a(2, a(0, a(0, a(0, a(1, 0)))))))) = a(3, a(3, a(3, a(2, a(0, a(0, a(0, a(0, 1)))))))) = a(3, a(3, a(3, a(2, a(0, a(0, a(0, 2)))))) = a(3, a(3, a(3, a(2, a(0, a(0, 3))))) = a(3, a(3, a(3, a(2, a(0, 4))))) = a(3, a(3, a(3, a(2, 5)))) = ...

Das ist für einige Zeit der einfachste Fall einer solchen Expansion, und es ist an Hand der Tabelle offensichtlich, warum Funktionswerte wie dieser selten direkt berechnet werden. Es ist auch interessant festzustellen, wie viele Schritte nötig sind, um schon sehr einfach aussehende Ackermann-Ausdrücke zu vereinfachen. Jede Zeile im vorigen Beispiel ist eine einzige Anwendung eines der drei Teile der Definition der Ackermannfunktion.

... = a(3, a(3, a(3, 13))) = ... = a(3, a(3, 65533))

Wenn wir an dieser Stelle mehrere logische Schritte überspringen, könnten wir $a(2,\; 5)$ zu 13 auswerten, und dann versuchen, $a(3,\; 13)$ auszuwerten – das ist 65533. Der nächste Funktionsaufruf, $a(3,\; 65533)$, liefert eine Zahl, die der Zahl der Atome im Universum entspricht, einige dutzend mal mit sich selbst multipliziert. Diese Zahl $n$ wird schließlich in die Berechnung $a(3,\; n)$ eingesetzt, die irgendwann zu einem Ausdruck der Form $a(2,\; a(2,\; a(2,\; \backslash dots\; a(2,\; 0)\backslash dots)))$ ausgeschrieben würde, die aber mit unseren Mitteln nicht mehr aufgeschrieben werden kann.

Der wirklich faszinierende Aspekt der Ackermann-Funktion ist, dass die einzige Berechnung, die neben den rekursiven Aufrufen tatsächlich auftaucht, die Berechnung von $a(0,\; n)$ ist, die einfach $n$ um 1 erhöht.

Sonstiges

---

Funktionswert a(4,2)

Des Öfteren wird vor allem im Internet der Funktionswert $a(4,2)$ in Form einer 19727-stelligen Dezimalzahl angegeben. Dieser kann wahrscheinlich noch nicht mit Hilfe der rekursiven Definition der Ackermannfunktion praktisch berechnet werden, weil zum Abspeichern der Zwischenergebnisse bei weitem zu viel Speicherplatz benötigt werden würde.

Die Funktion Fleißiger Biber

1962 gab Tibor Radó mit der Funktion Fleißiger Biber (busy beaver) eine noch stärker wachsende Funktion als die Ackermannfunktion an, die allerdings nicht mehr berechenbar ist.

Literatur

---

• Wilhelm Ackermann: Zum Hilbertschen Aufbau der reellen Zahlen. Math. Annalen 99 (1928), 118–133
• Yngve Sundblad: The Ackermann Function. A Theoretical, Computational, and Formula Manipulative Study. BIT 11 (1971), 107–119
• Uwe Schöning: Theoretische Informatik – kurzgefasst; Spektrum Akademischer Verlag, ISBN 3-8274-1099-1
• Dexter C. Kozen: The Design and Analysis of Algorithms. Springer 1992

Weblinks

---

• Einige Werte der Ackermannfunktion (Die Angaben für die Anzahl der Iterationen sind allerdings Unsinn)
• Beispielanwendung der Ackermannfunktion als Benchmark (Beachten Sie die große Zahl der Funktionsaufrufe schon bei der Berechnung kleiner Werte) (englisch)
• Dezimaler Wert von ack(4,2)
• Benchmarks von verschiedenen Computersprachen mit der Ackermannfunktion

Berechenbarkeitstheorie

Ackermannova funkce | Ackermann function | Función de Ackermann | Fonction d'Ackermann | Ackermann-függvény | アッカーマン関数 | Ackermannfunctie | Funkcja Ackermanna | Ackermann işlevi | Hàm số Ackermann | 阿克曼函數