Ackermannfunktion

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. Ihm zu Ehren wird diese Funktion heute Ackermannfunktion genannt. Sie kann von einem Computer in endlicher Zeit ausgewertet werden, ist aber nicht primitiv-rekursiv.

1935 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

Hierbei wird bei jedem Folgenglied die Operation des vorigen Folgenglieds -mal auf angewandt, also ist gerade , wobei die Variable -mal vorkommt und so weiter. Die Idee hinter der Ackermannfunktion ist es, diese Folge als Funktion aufzufassen.

Beispiel:

die man auch die Ackermannfunktion zu und nennt. Die letztgenannte Zahl liegt bereits weit jenseits von allem Vorstellbaren.

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

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:

Dabei ist eine weitere Funktion, die Ackermann nicht weiter beschrieb. Sie liefert die Startwerte :

Wenn man vom Wachstum der Ackermannfunktion spricht, meint man oftmals die Funktion .

Definition von Péter

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

Auch hier meint man im Zusammenhang mit Wachstumsuntersuchungen oftmals die Funktion , wenn man von der Ackermannfunktion spricht.

Aus dieser Definition ist nicht sofort ersichtlich, dass die Funktion für alle nicht negativen, ganzzahligen und definiert ist, da teilweise auch erhöht wird. Man kann aber erkennen, dass zum einen für wohldefiniert ist. Zum anderen ist unter der Voraussetzung, dass wohldefiniert ist, auch wohldefiniert, indem man die letzten beiden Rekursionsvorschriften iterativ benutzt.

Zu beachten ist allerdings, dass es bei einer Verringerung von keine obere Schranke für das Wachstum von in den folgenden Funktionsaufrufen gibt.

Modifizierte Ackermannfunktion

Häufig werden in der Komplexitätsanalyse leicht modifizierte Versionen der Ackermannfunktion verwendet, die jedoch das gleiche asymptotische Laufzeitverhalten aufweisen. Eine dieser Varianten, die eine Interpretation als „verallgemeinerte Exponentialfunktion“ erlaubt, kann wie folgt angegeben werden:

Die so definierte Folge von Funktionen können nun zu der Definition der modifizierten Ackermannfunktion verwendet werden, indem man

setzt.

Die Funktionen können nun als natürliche Fortsetzung der Addition, Multiplikation und Potenzierung interpretiert werden. So repräsentiert beispielsweise die -fache Addition der Zahl , die -fache Multiplikation der Zahl usw. Es gilt

Bedeutung in der theoretischen Informatik

Wie eingangs schon erwähnt, erfand Ackermann diese Funktion als Beispiel einer Funktion, die nicht primitiv-rekursiv, aber berechenbar ist.

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 (insbesondere eine Turingmaschine) 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 nachfolgender Beweis.)

Führt man auf der Klasse der primitiv-rekursiven Funktionen eine weitere Konstruktionsregel, die sogenannte µ-Rekursion, ein, erhält man eine größere Klasse ebenfalls berechenbarer Funktionen, die die Ackermannfunktion enthält. Man nimmt an, dass diese Klasse der µ-rekursiven Funktionen der Klasse der intuitiv berechenbaren Funktionen entspricht (Church'sche These).

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 , eine Funktion
• Sodann zeigt man durch strukturelle Induktion über den induktiven Aufbau der primitiv-rekursiven Funktionen, dass es zu jeder primitiv-rekursiven Funktion eine natürliche Zahl gibt, sodass für alle gilt: . Anschaulich zeigt 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:

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 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. Die Ackermann-Funktion ist daher eine einfache und sichere Methode, einen Stapelüberlauf zu provozieren, beispielsweise um zu testen, ob dieser Fehlerfall bearbeitet wird und ggf. wie dies erfolgt. Die Ackermann-Funktion hat dabei den Vorteil, dass sie immun gegen Compiler-Optimierungen ist und auch statische Quellcode-Analysen den (möglichen) Stapelüberlauf praktisch nicht detektieren können.

Diese Idee geht zurück auf Yngve Sundblad, der 1971 die Funktion benutzte, um diverse Programmiersprachen zu vergleichen. Um zu berechnen, werden Aufrufe getätigt.

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

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 durchführbar. Einen bedeutenden Zeitvorteil erhält man auch, wenn man direkt berechnet, statt es rekursiv zu zu expandieren. Die direkte Berechnung von erfordert lineare Zeit in . Die Berechnung von erfordert quadratische Zeit, denn sie führt zu (also für eine Konstante ; siehe Landau-Symbole) verschachtelten Aufrufen von für verschiedene . Die Berechnung von erfordert schließlich eine zu proportionale Zeit ().

Laufzeitabschätzungen mit der Umkehrfunktion

Da die Funktion sehr schnell wächst, wächst ihre Umkehrfunktion sehr langsam. Sie ist für jede praktisch vorstellbare Eingabegröße kleiner als 5, weil der Funktionswert größer als die Anzahl der Atome im Universum ist, wie die Berechnung von 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 andere Modifikationen leicht umdefiniert zu einer Funktion mit ähnlichem asymptotischen Verhalten. Diese modifizierten Funktionen sind nicht gleich der Ackermannfunktion, aber nach den Maßstäben der Laufzeitanalyse können sie als äquivalent betrachtet werden.

Implementierung

Die rekursive Implementierung der Ackermannfunktion (hier in Pseudocode) 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.

Grossman & Zeitman publizierten einen Algorithmus der ohne Zwischenspeicherung berechnet in Laufzeit , mit einem Speicherbedarf von .

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

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

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). 

Im Lambda-Kalkül ist sogar eine rein iterative Implementierung möglich. 1 und succ verwenden die Church-Numerale zur Darstellung der natürlichen Zahlen. Die Gleichungen der Definition von Péter lassen sich direkt durch β-Konversion zeigen.

 ack ≡ λn. n (λf.λm. m f (f 1)) succ 

Wertetabelle

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

Werte von

n \ m	0	1	2	3	4	...
0	1	2	3	4	5	...
1	2	3	4	5	6	...
2	3	5	7	9	11	...
3	5	13	29	61	125	...
4	13	65533	(Zahl mit 19729 Dezimalstellen)			...	(Potenzturm mit m+3 Zahlen)
5	65533
6

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.

Benötigter Speicher für , wenn als unsigned integer gespeichert.

m \ n	0	1	2	3	4	5
0	1 bit	2 bit	2 bit	3 bit	4 bit	16 bit
1	2 bit	2 bit	3 bit	4 bit	16 bit (2^4 bit)
2	2 bit	3 bit	3 bit	5 bit	8 KiB (2^16 bit)
3	3 bit	3 bit	4 bit	6 bit	≈2,504412...·10^19727 Byte (2^65536 bit = 2^65533 Byte)
4	3 bit	3 bit	4 bit	7 bit
5	3 bit	3 bit	4 bit	8 bit
6	3 bit	4 bit	4 bit	9 bit
7	4 bit	4 bit	5 bit	10 bit
8	4 bit	4 bit	5 bit	11 bit
9	4 bit	4 bit	5 bit	12 bit
10	4 bit	4 bit	5 bit	13 bit
100	7 bit	7 bit	8 bit	103 bit
1'000	10 bit	10 bit	11 bit	125⅜ Byte
10'000	14 bit	14 bit	15 bit	1250⅜ Byte
100'000	17 bit	17 bit	18 bit	≈12,5 KB (10^5 bit)
1'000'000	20 bit	20 bit	21 bit	≈125 KB (10^6 bit)
10'000'000	24 bit	24 bit	25 bit	≈1,25 MB (10^7 bit)
100'000'000	27 bit	27 bit	28 bit	≈12,5 MB (10^8 bit)
2^32−1	33 bit	33 bit	34 bit	≈512 MiB (2^32 bit)
2^64−1	65 bit	65 bit	66 bit	≈2 EiB (2^64 bit)

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. Es ist leicht zu erkennen, dass die Werte der ersten Zeile einfach eine Liste aller natürlichen Zahlen sind. Die jeweiligen Einträge können mit der Formel berechnet werden. Alle folgenden Zeilen enthalten einfach Anweisungen, in dieser Zeile einen Wert zu suchen. Im Falle der Zeile vereinfacht sich diese Anweisung dazu, den Wert in der Zeile 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 , 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 anhand 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 zu 13 auswerten und dann versuchen, auszuwerten – das ist 65533. Doch schon der nächste Funktionsaufruf liefert mit eine Zahl, die weit über die geschätzte Anzahl der Atome im Universum hinausgeht. Diese Zahl wird schließlich in die Berechnung eingesetzt, die irgendwann zu einem Ausdruck der Form ausgeschrieben würde, die aber mit unseren Mitteln nicht mehr aufgeschrieben werden kann.

Ein weiterer interessanter Aspekt der Ackermann-Funktion ist, dass die einzige Berechnung, die neben den rekursiven Aufrufen tatsächlich auftaucht, die Berechnung von ist, die einfach um 1 erhöht.

Literatur

• Wilhelm Ackermann: Zum Hilbertschen Aufbau der reellen Zahlen. In: Mathematische Annalen. Band 99, 1928, ISSN 0025-5831, S. 118–133, doi:10.1007/BF01459088 (uni-goettingen.de). 
• Jerrold W. Grossman, R. Suzanne Zeitman: An inherently iterative computation of Ackermann’s function. In: Theoretical Computer Science. Band 57, Nr. 2-3, Mai 1988, S. 327–330, doi:10.1016/0304-3975(88)90046-1. 
• Dexter C. Kozen: The Design and Analysis of Algorithms. Springer, Berlin 1992, ISBN 3-540-97687-6.
• Uwe Schöning: Theoretische Informatik – kurzgefasst. Spektrum Akademischer Verlag, Heidelberg 2001, ISBN 3-8274-1099-1.
• Yngve Sundblad: The Ackermann Function. A Theoretical, Computational, and Formula Manipulative Study. In: BIT – numerical mathematics. Springer, Dordrecht 11.1971, S. 107–119, ISSN 0006-3835.

Weblinks

• Erklärungsvideo zur Ackermannfunktion (englisch)

Einzelnachweise

1. Péter Rózsa: Konstruktion nichtrekursiver Funktionen. In: Mathematische Annalen, 111, 1935, S. 42–60
2. P. K. Agarwal, M. Sharir: Davenport-Schinzel sequences and their geometric applications. In: Handbook of computational geometry, 2000, S. 1–47.
3. Für Details zum Beweis sehe man z. B. im Buch von Uwe Schöning nach (siehe Literatur).
4. Jerrold W. Grossman, R.Suzanne Zeitman: An inherently iterative computation of ackermann's function. In: Theoretical Computer Science. 57. Jahrgang, Nr. 2–3, Mai 1988, S. 327–330, doi:10.1016/0304-3975(88)90046-1. 

Dieser Artikel wurde am 22. August 2004 in dieser Version in die Liste der exzellenten Artikel aufgenommen.