Ackermannfunktion

Die Ackermannfunktion ist eine 1926 von Wilhelm Ackermann erfundene, 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 ein ähnliches Wachstumsverhalten.

Entstehungsgeschichte

1926 vermutete David Hilbert, dass jede berechenbare Funktion primitiv-rekursiv ist. Vereinfacht gesprochen bedeutet dies, dass jede Funktion, die durch einen Computer berechnet werden kann, sich aus einigen wenigen sehr einfachen Regeln zusammensetzen lässt und die Dauer der Berechnung sich im Vorfeld abschätzen lässt. Dies trifft auf nahezu alle in der Praxis vorkommenden Funktionen zu. (Die Ausnahmen sind vorwiegend im Bereich des Compilerbaus zu finden.) Im gleichen Jahr 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 den gleichen Dienst erweist. Diese Funktion, gelegentlich auch als Ackermann-Péter-Funktion bezeichnet, wird heute vorwiegend benutzt.

Idee

Man betrachtet die Folge $a+b$, $a\cdot b$, $a^{b}$, $\ldots$ Hierbei wird bei jedem Folgeglied die Operation des vorigen Folgeglieds $b$ mal auf $a$ angewandt, also $a\cdot b$ ist gerade $a+a+\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 ist also eine Funktion, die die folgenden Gleichungen erfüllt:

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

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

$\phi (a,b,2)=a^{b}$

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle \phi(a,b,3) = a^{a^{.^{.^{.^{a}}}}} b-mal }

$\ldots$

Ab der fünften 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.

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

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

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

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

Beispiele:

• Möchte man $\phi (4,3,0)$ berechnen, so kann man die erste Zeile der Definition anwenden und erhält direkt: $\phi (4,3,0)=4+3=7$.
• Möchte man $\phi (4,0,2)$ berechnen, so kann man die zweite Zeile der Definition anwenden und erhält ebenfalls direkt: $\phi (4,0,2)=\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 $\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: $\phi (4,1,2)=\phi (4,\phi (4,0,2),1)$. $\phi (4,0,2)$ wurde aber gerade im vorigen Beispiel berechnet. Setzt man dies ein, so erhält man $\phi (4,1,2)=\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 sich in diesem Fall:

$\phi (4,1,2)$

$=\phi (4,\phi (4,0,2),1)$

$=\phi (4,1,1)$

$=\phi (4,\phi (4,0,1),0)$

$=\phi (4,0,0)$

$=4$

Wenn man vom Wachstum der Ackermannfunktion spricht, meint man oftmals die Funktion $f(n):=\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 $\psi$ auskommt:

$a(0,m)=m+1$

$a(n+1,0)=a(n,1)$

$a(n+1,m+1)=a(n,a(n+1,m))$

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

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, mit anderen Worten 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, die einen solchen Nachweis einfacher führen lassen. 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 die Ackermannfunktion, von der man nachweisen kann, dass sie berechenbar ist, aber nicht primitiv-rekursiv. (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.

Beweisskizze zur Behauptung, dass die Ackermannfunktion nicht primitiv-rekursiv ist: Als erstes definiert man zu jeder primitiv-rekursiven Funktion g eine Funktion $f_{g}(n):=\max\{g(n_{1},...,n_{k}):\sum _{i=1}^{k}n_{i}\leq n\}$ Diese Funktion gibt das Maximum an, das man mit g erreichen kann, wenn die Summe der Argumente n nicht überschreitet. Sodann zeigt man durch strukturelle Induktion über den induktiven Aufbau der primitiv-rekursiven Funktionen, dass es zu jeder primitiv-rekursiven Funktion g eine natürliche Zahl k gibt, sodass für alle n ≥ k gilt: fg(n) < a(k,n). Anschaulich bedeutet dies, dass die Ackermannfunktion stärker wächst als jede primitiv-rekursive Funktion. Damit beweist man dann wie folgt, dass die Ackermannfunktion nicht primitiv-rekursiv ist: Angenommen, a(n,k) sei primitiv-rekursiv, dann auch g(n) := a(n,n). Nach der Vorbemerkung gibt es aber ein k, sodass für alle n ≥ k gilt: g(n) < a(k,n). Setzt man hier n = k so erhält man den Widerspruch: $g(k)\leq f_{g}(k)<a(k,k)=g(k)$ Für Details zum Beweis sehe man z.B. im Buch von Schöning nach. (Siehe Literatur)

Anwendungen

Für die Ackermannfunktion gibt es nur sehr wenige Anwendungen. Die zwei wichtigsten sind als Benchmarktest für rekursive Aufrufe in Programmiersprachen und für die Laufzeitabschätzung im Zusammenhang mit der Union-Find-Datenstruktur.

Benchmark für rekursive Aufrufe

Bei der Einführung von neuen Programmiersprachen, Compilern und Computern möchte man deren Leistungsfähigkeit untersuchen. Eine Möglichkeit hierfür sind Benchmarktests, bei denen ein spezielles Programm benutzt wird, um bestimmte Eigenschaften zu überprüfen.

In diesem Zusammenhang wird die Ackermannfunktion gerne als Benchmark zur Überprüfung von rekursiven Prozeduraufrufen 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 Stack Overflow führt, also dazu, dass dem System der Speicher ausgeht.

Diese Idee geht zurück auf Yngre 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)+1=2^{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,\dots a(1,0)\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\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ätzung bei Union-Find

Da die Funktion $f(n):=a(n,n)$ sehr schnell wächst, wächst ihre Umkehrfunktion sehr langsam. Diese Umkehrfunktion taucht in der Laufzeitanalyse bestimmter Algorithmen auf, zum Beispiel beim Union-Find-Problem. In diesem und anderen Zusammenhängen wird die Ackermannfunktion oft leicht umdefiniert zu einer Funktion mit ähnlichem asymptotischem Verhalten. Diese modifizierten Funktionen sind nicht äquivalent zur Ackermannfunktion, aber nach den Maßstäben der Laufzeitanalyse können sie als äquivalent betrachtet werden. Die Umkehrfunktion der Funktion f ist für jede vorstellbare Eingabegröße kleiner als 4, kann also in der praktischen Analyse von Algorithmen als konstant betrachtet werden.

Implementation

In der Programmiersprache C++ mit den Datenstrukturen der Standard Template Library lässt sich die Ackermannfunktion wie folgt ohne Rekursion implementieren:

int ack(int x, int y)
{
  std::stack<int> stack;
  while (x > 0 || !stack.empty())
  {
    if (x == 0)
    {
      x = stack.top();
      stack.pop();
      y = y + 1;
    }
    else if (y == 0)
    {
      y = 1;
      x = x - 1;
    }
    else
    {
      y = y - 1;
      stack.push(x - 1);
    }
  }
  return y + 1;
}

Die Rekursion wird dabei durch einen Stack simuliert.

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\cdot 2^{m}-3$
4	13	65533	$2^{65536}-3\approx 2\cdot 10^{19728}$ ¹	$a(3,2^{65536}-3)$	$a(3,a(4,3))$	$2^{2^{\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,2))$
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

Genauere Betrachtung

An Hand 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 dahingehend, 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 nun offensichtlich, warum Funktionswerte wie dieser in der obigen Tabelle 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. 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, der irgendwann zu einem Ausdruck der Form $a(2,a(2,a(2,\dots a(2,0)\dots )))$ ausgeschrieben würde, der 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)

Es sei noch festgehalten, dass der Funktionswert a(4,2), der in Form einer 19727-stelligen Dezimalzahl auf verschiedenen Internetseiten auftaucht, wahrscheinlich nicht mit der rekursiven Definition der Ackermannfunktion praktisch berechnet werden kann, weil dafür bei weitem zu viel Speicherplatz für die Zwischenergebnisse benötigt würde.

Die Busy-Beaver-Funktion

1962 gab Tibor Radó mit der Busy-Beaver-Funktion (fleißiger Biber) 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
• Yngre 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)