Zum Inhalt
Alle Apps

Ackermann-Funktion

Über diese App

Drei harmlose Rekursionsregeln, ein explodierender Berg: Rekursionskette und Stapeltiefe von A(m,n) live abspielen und scrubben, in der Wachstums-Matrix erleben, wie m die Operation eine Etage höherschaltet (Nachfolger → Addition → Multiplikation → Potenz → Potenzturm) — und bei m=4 verweigert der Computer mit Ansage: A(4,2) hat 19.729 Stellen.

Mit Erklärmodus: Ein KI-Tutor führt dich durch die App, zeigt in der Szene, worauf es ankommt, und beantwortet deine Fragen.

Drei Regeln, enormes Wachstum

Die Ackermann-Funktion ist durch drei Regeln definiert: A(0, n) = n + 1, A(m, 0) = A(m − 1, 1) und A(m, n) = A(m − 1, A(m, n − 1)). Sie ist für alle natürlichen Zahlen berechenbar und endet immer, wächst aber schneller als jede primitiv-rekursive Funktion. Der erste Parameter schaltet die Rechenart eine Stufe höher: m = 0 ist der Nachfolger, m = 1 entspricht einer Addition, m = 2 einer Multiplikation, m = 3 einer Potenz und m = 4 einem Potenzturm. A(4, 2) = 2^65536 − 3 hat bereits 19.729 Dezimalstellen.

Was die App zeigt

Links läuft die Rekursion live: Die drei Regeln leuchten auf, sobald sie greifen, eine Kette farbiger Aufrufe zeigt die aktuelle Verschachtelung, und ein Berg zeichnet die Stapeltiefe über alle Schritte, mit markiertem Gipfel. Oben steht das Ergebnis. Rechts zeigt eine Wachstums-Matrix A(m, n) für jede Etage mit dem Namen der Operation. Für m = 4 ab n = 1 verweigert die App die Animation und zeigt stattdessen die Größe der Zahl.

Selbst ausprobieren

Wähle m von 0 bis 4 und n von 0 bis 5, spiele die Rekursion ab, gehe Schritt für Schritt vor oder ziehe die Abspielposition durch den Berg. Das Tempo reicht von einem bis zu 10.000 Schritten pro Sekunde. Vergleiche A(2, 3) mit A(3, 3) und beobachte, wie der Berg in die Höhe schießt.

Häufige Fragen

Wie ist die Ackermann-Funktion definiert?
A(0, n) = n + 1; A(m, 0) = A(m − 1, 1) für m > 0; A(m, n) = A(m − 1, A(m, n − 1)) für m, n > 0. Diese drei Regeln genügen, um die Funktion für alle natürlichen Zahlen m und n auszurechnen.
Warum ist die Ackermann-Funktion nicht primitiv rekursiv?
Primitiv-rekursive Funktionen kommen mit Schleifen aus, deren Durchlaufzahl vorab feststeht. Für jede solche Funktion gibt es ein m, ab dem A(m, ·) schneller wächst. Die Ackermann-Funktion ist deshalb berechenbar und total, lässt sich aber nicht mit vorab begrenzten Schleifen ausdrücken.
Wie groß ist A(4, 2)?
A(4, 2) = 2^65536 − 3, eine Zahl mit 19.729 Dezimalstellen. Schon A(4, 1) = 65533, A(4, 3) = 2^(2^65536) − 3 ist so groß, dass sich ihre Ziffern nicht ausschreiben lassen.
Was kann ich in der Ackermann-App beobachten?
Wie jede Regel greift, wie die Aufrufkette wächst und schrumpft und wie hoch der Stapel wird, für frei gewählte m und n. Die Wachstums-Matrix zeigt, welche Rechenart jede Etage m darstellt, und bei m = 4 die Größe der Ergebnisse.

Fach: Informatik

Mehr aus Informatik

Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps