Richtig große Zahlen (und die Ackermannfunktion)

Ein Blogeintrag für mich: Ein Thema hat mich interessiert, ich habe recherchiert und zusammengefasst, um es mir anzueignen. Für die Leser, die dableiben: Es geht um richtig große Zahlen. So große, dass die Rechenarten Addition, Multiplikation und Potenzierung nicht reichen.

Ein bisschen was zu den Rechenarten und wie sie zusammenhängen:

  • Die Addition ist eine der Grundrechenarten. Zum Beispiel: 1+2 oder 3+4.
  • Nicht ganz so grundrechnend ist die Multiplikation, die quasi nur eine Abkürzung für die mehrfache Addition ist:
    3*4 ist ja nichts anderes als 3+3+3+3 (also vier 3er mit einem Plus dazwischen).
    Fußnote: 3*4 ist natürlich auch 4+4+4, aber aus Gründen, die in den nächsten Zeilen klarer werden, lese ich hier von rechts nach links.
  • Noch weniger grundrechnend ist die Potenzierung, die quasi nur eine Abkürzung für die mehrfache Multiplikation ist:
    34 ist ja nichts anderes als 3*3*3*3 (also vier 3er mit einem Mal dazwischen).

Und was kommt nach der Potenzierung? Gibt es auch eine Abkürzung für die mehrfache Potenzierung? Ja, gibt es. Die heißt Tetration. Deshalb:

  • Noch weniger grundrechnend ist die Tetration, die quasi nur eine Abkürzung für die mehrfache Potenzierung ist:
    43 ist nichts anderes als 3333 (also vier 3er mit einem Hoch dazwischen).

Und was kommt nach der Tetration? Wie auch immer es heißt, etwa 3 dingens 4, es wird quasi nur eine Abkürzung für die mehrfache Tetration sein. 3 dingens 4 ist nichts anderes als vier 3er mit einem Tetra dazwischen: 3333. Aber spätestens jetzt wird es mit der Schreibung und eventueller Klammersetzung extrem verwirrend.

Also gut: Neue Schreibung. Zum Beispiel den Hyper-Operator:

  • 3(1)4 ist 3+4=7, also die Addition, die unterste Ebene, wie oben.
  • 3(2)4 ist 3*4=12, die Multiplikation, eine Ebene drüber.
  • 3(3)4 ist 34=81, die Potenzierung, die nächste Rechenoperation.
  • 3(4)4 ist 43=37625597484987 (der Rechner versagt), die Tetration.
  • 3(5)4 ist das, wo wir oben aufgehört haben. Heißt manchmal Pentation.

Und natürlich kann man auch mit höheren Zahlen weitermachen. Was etwa bei 3(20)4 herauskommt, kann man nicht mal im Ansatz begreifen.
Vielleicht hilft eine weitere Schreibweise, die Pfeilnotation von Donald Knuth. Bei ihr gilt:

  • 3↑4 ist dasselbe wie 3(3)4, also 34.
  • 3↑↑4 ist dasselbe wie 3(4)4, also 43. Man kann 3↑↑4 auch schreiben als 3↑3↑3↑3. Das ist die riesige Zahl von oben.
  • 3↑↑↑4 ist dasselbe wie 3(5)4, auch zu schreiben als 3↑↑3↑↑3↑↑3.
  • 3↑↑↑↑4 ist dasselbe wie 3(6)4, auch zu schreiben als 3↑↑↑3↑↑↑3↑↑↑3.

Und so weiter. Eine weitere Schreibweise ist die als Funktion. So wie man die Addition als Funktion schreiben kann – addition(a,b) – kann man auch den Hyper-Operator als Funktion schreiben: hypern(a,b) = hyper(a,n,b) = a(n)b = a↑n-2b

Man sieht, dass der Hyper-Operator sehr schnell sehr große Zahlen erzeugt. Wie schnell und wie groß?
Im Zusammenhang mit dieser Frage und aus Gründen, auf die ich unten in einem Anhang eingehen werde, konstruierte 1926 Wilhelm Ackermann die Ackermann-Funktion. In Kreisen der theoretischen Informatik ist sie sehr bekannt; praktisch findet sie wenig Anwendung – allerdings wird sie manchmal als Benchmark fürs Testen von Computern benutzt. Dafür ist sie geeignet, weil sie sehr schnell sehr viel Rechenzeit erfordert. Die Ackermann-Funktion ist berühmt dafür, dass sie sehr, sehr schnell große Werte erzeugt. Die Ackermann-Funktion wurde entworfen, um folgende Bedingungen zu erfüllen:

ack(a,b,1) = a*b (Multiplikation)
ack(a,b,2) = ab (Potenzierung)
ack(a,b,3) = ba (Tetration)

Und so weiter. Das ist jetzt aber noch keine Definition der Funktion, das ist nur eine Beschreibung ihrer Eigenschaften und ihres Bauprinzips. Die eigentliche Funktionsdefinition sah anders aus. Inzwischen ist sie mehrfach vereinfacht worden. Die heute verbreitete Funktionsdefinition erfüllt immer noch das allgemeine Bauprinzip, kommt aber mit zwei Argumenten aus und sieht so aus:

  1. ack(0, m) = m+1
  2. ack(n+1, 0) = ack(n,1)
  3. ack(n+1, m+1) = ack(n, ack(n+1,m))

Die erste Zeile wendet man an, wenn mindestens der erste Funktionsparameter 0 ist, die zweite Zeile, wenn genau der zweite Parameter 0 ist, die dritte in allen anderen Fällen. Die Funktion ist rekursiv definiert, das heißt zum Beispiel, dass man ack(1,0) erst ausrechnen kann, wenn man vorher ack(0,1) ausgerechnet hat (laut Zeile 2), was wiederum gleich 2 ist (laut Zeile 1).

Um ack(2,1) auszurechnen, muss man erst ack(1,ack(2,0)) (Zeile 3) ausrechnen,
was sich ist ack(1,ack(1,1)) (Zeile 2),
was sich ist ack(1,ack(0,ack(1,0))) (wieder Zeile 3),
was sich ist ack(1,ack(0,ack(0,1))) (Zeile 2),
was sich ist ack(1,ack(0,2)) (Zeile 1),
was sich ist ack(1,3) (Zeile 1),
was sich ist ack(0,ack(1,2)) (Zeile 3),
was sich ist ack(0,ack(0,ack(1,1))) (Zeile 3),
was sich ist ack(0,ack(0,ack(0,ack(1,0))) (Zeile 3),
was sich ist ack(0,ack(0,ack(0,ack(0,1))) (Zeile 2),
was sich ist ack(0,ack(0,ack(0,2)) (Zeile 1),
was sich ist ack(0,ack(0,3)) (Zeile 1),
was sich ist ack(0,4) (Zeile 1),
was sich ist 5 (Zeile 1).

Puh. Viel Rechenarbeit, aber wenn man es mal selber durchexerziert hat, erkennt man das Prinzip dahinter. Beispiele für das Wachstum der Ackermannfunktion:

ack(4,0) = 13
ack(4,1) = 65533
ack(4,2) = 265536-3 (eine Zahl mit 19727 Dezimalstellen).

Oft meint man, wenn man vom Wachstum der Ackermannfunktion spricht, die Funktion f(n) = ack(n,n). Deren erste Werte sind:

f(0) = ack(0,0) = 1
f(1) = ack(1,1) = 3
f(2) = ack(2,2) = 7
f(3) = ack(3,3) = 61
f(4) = ack(4,4) = ack(3,265536− 3) – zu groß, um sie anders darzustellen.

Wie müssen dann erst ack(5,5) oder ack(6,6) oder noch größere Zahlen ausschauen? The mind boggles. Dass die Ackermannfunktion so schnell wächst, ist um so interessanter, als die einzige Rechnung, die darin vorkommt, die Addition um den Wert 1 ist. Die hohen Werte kommen nur von der massiven Rekursion, dem wiederholten und wiederholten und wiederholten Aufruf der Funktion.

Hier sieht man, was die Ackermannfunktion mit dem Hyper-Operator und mit den Grundrechenarten zu tun hat, mit denen dieser Blogeintrag angefangen hat:
ack(m,n) = hyper(2,m,n+3)-3
Das ist ein bisschen mathematisch. Deshalb hier ausformuliert:

ack(0,n) = n+1
ack(1,n) = (2 plus (n+3)) -3
ack(2,n) = (2 mal (n+3)) -3
ack(3,n) = (2 hoch (n+3)) -3
ack(4,n) = (2 ↑↑ (n+3)) -3
ack(5,n) = (2 ↑↑↑ (n+3)) -3

Inzwischen wurden Funktionen gefunden, die noch schneller wachsen als die Ackermann-Funktion. Auch dazu steht unten noch ein Anhang.

Jetzt noch ein paar Zuckerstückchen für die Leser, die durchgehalten haben:

  • Eine erwähnenswert große Zahl ist Grahams Zahl, „die größte jemals in einem mathematischen Beweis [sinnvoll] verwendete Zahl“. Die Zahl ist so groß, dass man sie auch mit dem Hyper-Operator nicht sinnvoll hinschreiben kann.
  • Wie komme ich auf diesen Kram? Unter anderem über diese Liste besonderer Zahlen in der Wikipedia.
  • Oben habe ich die ersten Ackermann-Werte für ack(n,n) angegeben: 1, 3, 7, 61 – die nächste Zahl ist bereits zu groß. Einfacher ist diese berühmte Zahlenreihe: 1, 1, 2, 3, 5, 8, 13 – welche Zahl kommt da als nächste? Man muss nur wissen, wo man nachschaut, in der On-Line Encylopedia of Integer Sequences (Wikipedia, hier der direkte Link zum Eingabefeld). Das ist ein Nachschlagewerk für Zahlreihen. Man gibt einen Ausschnitt aus einer solchen Reihe ein, und die Enzyklopädie spuckt aus, wo in der Mathematik diese Reihe auftaucht.
  • Für Fans großer Zahlen: So mindboggling wie die Zahlen oben sind, noch viel, viel größer ist The Clarkkkkson. Ausgangspunkt waren abzuschreibende Zeilen als Strafe im Unterricht („Lynz“ = lines), drumrumgebastelt wurde mit Hyper-Operatoren und Hyper-Fakultät, herausgekommen ist eine Zahl, die immer noch unvorstellbarer groß wird. Wer’s mag, der liest das wie eine immer mit sich selber wetteifernde Lügen- und Übertreibungs-Geschichte. (Aber das bin vermutlich nur ich.) Und doch ist The Clarkkkkson immer noch genauso weit von unendlich entfernt wie jede andere Zahl. Am Schluss des Aufsatzes steht ein Aufruf, selber noch auf anderen, vergleichbaren Wegen eine noch größere Zahl zu erfinden. Ich könnt’s nicht, klingt aber nach einem Facharbeitsthema.

ANHANG 1: Primitiv-rekursive Funktionen.

Tatsächlich ist auch die Addition, mit der oben alles angefangen hat, gar nicht so grundlegend, sondern kann auf weitere, noch primitivere Rechenformen zurückgeführt werden. Alle Funktionen, die auf diese primitiven Rechenoperationen zurückgeführt werden können, heißen primitiv-rekursive Funktionen. (Was genau diese grundlegenden Formen sind, würde jetzt verwirren. Zumindest mich.)
Zu diesen primitiv-rekursiven Funktionen gehört alles, was man sich so im Alltag und um den Alltag herum unter einer Funktion vorstellt. Dazu gehört eben auch die Summenfunktion add(a,b). Und demnach auch die Multiplikationsfunktion multi(a,b). Und demnach auch die Potenzfunktion pot(a,b). Und die Tetration tetra(a,b). Und so weiter.
All diese Funktionen kann man mit einem nicht-rekursiven Computerprogramm berechnen, das nicht viel mehr enthalten muss als Addition und Subtraktion, als Variablen und eine Zählschleife – also eine Schleife, bei der man am Anfang sagt: wiederhole 4 mal, oder 5 mal, oder wieviel auch immer.
Die Frage war nun: Gibt es Funktionen, die nicht primitiv-rekursiv sind? Die man nicht mit einem solchen Computerprogramm berechnen kann? Die Ackermann-Funktion ist eine solche Funktion und sollte genau das demonstrieren. Um die Ackermann-Funktion imperativ zu programmieren, braucht man eine while-Schleife, mit Zählschleife ist das nicht möglich. Sie wächst zu schnell.
Die Ackermann-Funktion gehört zu den μ-rekursiven Funktionen. Die μ-rekursiven Funktionen sind alle die, die man mit einer Turingmaschine berechnen kann und umgekehrt, und ebenso die while-berechenbaren Funktionen, und umgekehrt.

Manche Funktionen wachsen so schnell, dass man sie nicht mal mehr damit berechnen kann. Zum Beispiel die Sache mit dem fleißigen Biber.


ANHANG 2: Fleißige Biber.

Die Erklärung, was eine Turingmaschine ist, kündige ich immer wieder an. Irgendwann kommt das auch noch. Kurz: Es ist eine bestimmte Art erdachter Maschine, die man auch aus Legosteinen oder was auch immer konstruieren kann, die man sich aber meist nur als Simulation auf dem Computer oder als Definition auf dem Papier anschaut.
Zur Definition, und quasi zur Programmierung dieser Maschine, gehört eine beliebig große Reihe von Zuständen, die die Maschine einnehmen kann. Anhand dieser Zustände schreibt die Maschine dann Zeichen auf ein prinzipiell endloses Band, ähnlich wie ein Fernschreiber.

Die Frage ist nun: Wie oft kann eine Turingmaschine mit n Zuständen und als einzigen möglichen Zeichen {0, 1} das Zeichen 1 das Band schreiben? Es ist leicht, Turingmaschinen zu programmieren, die unendlich viele 1er schreiben, aber die zählen nicht.

Antwort:

  • Eine Turingmaschine mit 1 Zustand und dem Alphabet {0,1} kann das Zeichen 1 maximal 1mal aufs Band schreiben. (Eine Maschine, die das auch tut, heißt „fleißiger Biber“.)
  • Eine Turingmaschine mit 2 Zuständen kann das Zeichen 1 maximal 4mal aufs Band schreiben. (Eine Maschine, die das auch tut, heißt „fleißiger Biber“.)
  • Eine Turingmaschine mit 3 Zuständen kann das Zeichen 1 maximal 6mal aufs Band schreiben. (Eine Maschine, die das auch tut, heißt „fleißiger Biber“.)
  • Eine Turingmaschine mit 4 Zuständen kann das Zeichen 1 maximal 13mal aufs Band schreiben. (Eine Maschine, die das auch tut, heißt „fleißiger Biber“.)
  • Eine Turingmaschine mit 5 Zuständen kann das Zeichen 1 maximal… man weiß es nicht. Mindestens 4098mal, aber ist das bereits ein fleißiger Biber oder gibt es noch bessere Maschinen?
  • Eine Turingmaschine mit 6 Zuständen kann das Zeichen 1 maximal… man weiß es nicht. Auf jeden Fall mehr als 4,64×101439mal.

(Alle Daten aus Wikipedia.)

Die Fleißiger-Biber-Funktion biber(n) gibt an, wieviele 1er eine Turingmaschine mit n Zuständen und dem Alphabet {0,1} aufs Band schreiben kann. Diese Funktion ist sauber definiert, aber nicht berechenbar; sie wächst schneller als jede berechenbare Funktion. Das kapiere ich noch nicht ganz, wird aber wohl stimmen.


ANHANG 3: Noch mehr zur Ackermannfunktion.

Ich komme nicht los von ihr. Gerade habe ich zwei Seiten vollgekritzelt, mit Bleistift, mit Berechnungen für verschiedene Ausgangswerte. Langsam dämmert es. Mathematische Zusammenhänge kann man sich ähnlich erschließen wie Gedichte, und ich finde sie ähnlich schön.

  • ack(0,n) ist immer gleich n+1. Das ist sozusagen die Sukzession, die Nachfolgerfunktion: ack(0,8) ist 9, ack(0, 20) ist 21.
  • ack(1,3) hat etwas mit Addition zu tun – dafür steht der erste Parameter, die 1.
    ack(1,3) =
    ack(0,(ack(1,2)) =
    ack(0,ack(0,ack(1,1))) =
    ack(0,ack(0,(ack(0,ack(1,0)))) =
    ack(0,ack(0,(ack(0,ack(0,1)))) – der zweite Parameter, hier die 3, gibt also an, wie oft die Sukzessor-Funktion aufgerufen wird (und zwar, indem der Parameter bei jedem Aufruf um eins verringert wird), bis die ganze Reihe nur noch aus Sukzessor-Funktionen besteht. Die Addition wird also auf wiederholte Sukzession zurückgeführt.
  • Ähnlich wird die Multiplikation ack(2,n) auf die wiederholte Addition zurückgeführt: ack(2,1) führt irgendwann zu ack(1,3) führt irgendwann zu ack(0,4) = 5. Oder: ack(2,2) führt irgendwann zu ack(1,5) führt irgendwann zu ack(0,6) = 7. Und: ack(2,3) = ack(1,9) = ack(0,10) = 11.
    Ausführlicher:
    ack(2,3) =
    ack(1,(ack(2,2)) =
    ack(1,(ack(1,ack(1,(2,1)) =
    ack(1,(ack(1,ack(1,ack(2,0))
    Also so ähnlich wie oben, nur doch anders.

Nachvollziehen kann man das erst, fürchte ich, wenn man auch zwei Seiten vollgekritzelt hat. Muss aber wirklich nicht sein wegen mir.

Auch grafisch kann man die Ackermannfunktion auf sich wirken lassen. Hier ist (mit Lupe) die vermutlich auch noch fraktale Ausformulierung von ack(3,2):

(ack(3,2) als Textdatei herunterladen)

Besonders die jeweils letzte Ziffer ist beachtenswert.
Für mich ist das Versuchen, die unverkennbare Ordnung hinter den Zeichen zu begreifen, vergleichbar mit dem Versenken in ein Yantra (eine Art Mandala nur mit geometrischen Formen) wie dieses hier:

sri_yantra

(Quelle: Wikipedia, unter CC AT-SA 2.5) Nicht dass ich mich damit je länger als ein paar Minuten beschäftigt hätte. Es hat ein wenig von: „wie viele Dreiecke sind in dieser Zeichnung enthalten“?

Und zuletzt kann man auch noch die Zeichenketten einfach als solche betrachten. Mit den folgenden Regeln kann man sich Ackermann-Aufrufe übersetzen:
„ack“ => 2
„1,“ => plus
„2,“ => mal
„3,“ => hoch
jede Zahl direkt nach einem Komma (es gibt genau eine einzige davon pro Zeile) wird um 3 erhöht.
Am Zeilenende schreibt man noch mal -3 hin und setzt Klammern um das vorhergehende..

Damit gilt:
ackermann

Also 29.
Ich höre jetzt mal auf damit, bevor man mich noch des Wahnsinns verdächtigt.


Allerletzter Nachtrag, versprochen:

Die 3. Zeile der Funktionsdefiniton lautet:

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

Und jetzt verstehe ich sie fast. Ich setze ein paar Zahlen und Zeichen ein:

ack(2, 4) = ack(1, ack(2,3))

und ersetze zur Veranschaulichung das erste Argument durch das gemeinte Rechenzeichen:

ack(*, 4) = ack(+, ack(*,3))

Und das heißt dann vereinfacht: Die x-fache Multplikation von 2 ist gleich 2 plus die (x-1)-fache Multiplikation von 2, etwa:

2*4 = 2+(2*3)

Oder mit einem höheren ersten Argument.

2 hoch 7 = 2 mal (2 hoch 6)

Und mit diesem Kellnerpunkt soll jetzt endgültig Schluss sein.

Kellnerpunkt: „Er ergab sich immer dann, wenn ein pompös überdrehtes Gespräch aus den Höhen seiner Selbstgefälligkeit zu einer entlarvend primitiven Schlußfolgerung abglitt, die sogar dem Kellner einleuchten mußte.“ (Friedrich Torberg, aus der Tante Jolesch. Will nichts gegen Kellner gesagt haben, es ist halt so, dass der halt nur den Schlusspunkt der Diskussion mitkriegt.)

20 Antworten auf „Richtig große Zahlen (und die Ackermannfunktion)“

  1. Ich bin ganz am Anfang hängen geblieben: ich dachte 3*4 bedeutet 4+4+4 und nicht 3+3+3+3? Habe gerade alle mir bekannten Sprachen durchgedacht und alle besagen es so, meine ich?

  2. Hande, das ist mir auch aufgefallen, aber mir fiel kein Weg ein, es zu vermeiden. 3*4 heißt natürlich beides, 4+4+4 und 3+3+3+3, und bei beidem kommt ja das gleiche heraus. Meistens und in allen Sprachen liest man bei der Multiplikation von links nach rechts (obwohl es egal ist), bei allem, was danach kommt, liest man aber von rechts nach links und deshalb wollte ich das auch schon bei der Multiplikation so machen.

    Ich habe das oben durch eine Ergänzung zu klären versucht.

    Mir war dieser Zusammenhang wichtig:
    3*4 ist eben die Addition von 4 Dreiern hintereinander, so wie
    3^4 die Multiplikation von 4 Dreiern hintereinander ist, so wie
    3^^4 die Potenzierung von 4 Dreiern hintereinander ist.

    (Wie sieht es mit Sprachen aus, die von rechts nach links gelesen werden? Steht bei der Potenz der Exponent auch rechts; wird bei der Multiplikation intuitiv von rechts nach links interpretiert?)

  3. Schönster Satz für mich: „Das kapiere ich noch nicht ganz, wird aber wohl stimmen.“

    Bei solchen Einträgen von dir bin ich mir nicht völlig sicher, ob ich nur zu faul bin zum Mitdenken oder ob das meinen intellektuellen Horizont übersteigt. Ich will es vorläufig noch nicht genau herausfinden. Schwebezustände haben manchmal einen eigenen Charme ;-)

  4. Heißt ja auch nicht LdL, Lernen durch Lesen… :-)

    Ich denke, es ist illusorisch, die Ackermannfunktion (oder auch formale Sprachen) in der Länge eines Blogeintrags so zusammenfassen zu wollen, dass man sie verstehen kann. Ich habe ganze Vorlesungen darüber gehört. Allerdings traue ich mir inzwischen tatsächlich zu, das richtig gut und nachvollziehbar zu erklären – aber das geht nicht in ein paar Blogeinträgen. So ein einführender Aufsatz, zwanzig Seiten, mit Übungen dazu, ein Bleistift gleich beiliegend… aber dafür gibt’s keinen Markt, glaube ich.

    Die Beiträge können nur a) mir Gelegenheit gegeben, mein Wissen zu festigen, b) jemandem, der schon mal ein bisschen was davon gehört hat, aber nicht ganz firm ist, einen Zugang geben und c) vielleicht demonstrieren, dass theoretische Informatik zumindest irgendwem Spaß macht. Ach ja, und vor allem: d) dass Lehrer sich auch über das Nötigste hinaus mit ihren Fachinhalten beschäftigen. Auch wenn ich das von bloggenden Lehrern sowieso kenne.

  5. …komisch das der Ackermannwitz gar nicht aufgetaucht ist. War mein erster Einfall als ich von Ackermann und großen Zahlen las…kein wunder, dass die Funktion so heißt und so…aber vielleicht bringt einen so ein blöder gedanke auch nur raus…ich probiers morgen nochmal komplett zu verstehen…ohne den Banker-Lenker

  6. Tatsächlich wollte ich ursprünglich anfangen mit: „‚Finanzkrise vernichtet laut neuer Studie $ 50 000 000 000 000‘. Das sollen große Zahlen sein?“ Schien mir dann aber doch nicht angebracht.

  7. Wow. Ich kann’s kaum glauben, dass ich sowas mal studiert habe. Danke für den „trip down memory lane“.

    Die Sache mit dem Clarkkkkson scheint mir aber eine trickreiche Lehrerfinte zu sein: Um die Strafarbeit zu vermeiden, haben die Schüler sich mit großen Zahlen und sogar Hyperfunktionen beschäftigt – und dabei was gelernt, obwohl sie das gar nicht wollten ;-).

  8. Ein Dejvu… aber als Blogbeitrag ist das Ganze leichter erträglich (als es damals in der Vorlesung zu ertragen war) :-)

  9. Wir hatten das damals als Do-It-Yourself-Übungsaufgabe. Wir haben überhaupt eigentlich alles als Übungsaufgabe aufbekommen. War eine harte Zeit das Vorstudium. Im Hauptstudium wird’s dann wieder leichter :) – bis auf gewisse Lehrstühle…

    Liest man wirklich die Multiplikation in allen Sprachen von Links nach Rechts ??? – ich hätte gedacht wenigstens im Arabischen wäre es anders. Sind aber eh alle symmetrisch, also egal.

  10. „Liest man wirklich die Multiplikation in allen Sprachen von Links nach Rechts ??? – ich hätte gedacht wenigstens im Arabischen wäre es anders.“

    Eben, diese Frage habe ich auch gestellt. Nur bringt googeln nach „arabisch“ und „Zahlen“ aus verständlichen Gründen nicht das richtige Ergebnis…

    (Bei der Multiplikation von Matrizen spielt es übrigens eine Rolle, da gilt das Kommutativgesetz nicht.)

  11. Wow, ein super Eintrag. Besonders Anhang 3 hat mich von den Zusammenhängen her wirklich weitergebracht. Und nicht zuletzt die ack(3,2)-Grafik ist toll :)

  12. Lieber Thomas,

    ich hatte vor längerem etwas über die Ackermannfunktion gelesen, dann wieder vergessen (samt Quelle) und jetzt wieder gesucht. Ich fand deine Internetseite dazu sehr anschaulich, danke dafür. Zum Weiter/Parallel-Lesen empfehle ich eine Seite, wo eine nicht rekursive Berechnungsvorschrift angegeben wird. Ich habe sie noch nicht nachgerechnet und hoffe, dort stimmt alles:

    http://www.delphipraxis.net/55778-iterative-ackermannfunktion-und-sie-gibt-es-doch-puh.html

    Uwe

  13. Danke für den Link. Und klar, jede rekursiv programmierbare Funktion lässt sich auch in einer äquivalenten iterativen Form schreiben. Im Studium mussten wir einen Algorithmus dafür lernen und anwenden (Details längst vergessen, aber Prinzip weiß ich noch), und außerdem steht nach dem Übersetzen in Maschinensprache ja ohnehin ein iteratives Programm da, weil es auf dieser Ebene keine Rekursion gibt.

  14. Ich habe das erst heute gelesen, durch den Pingback mit einem neueren Post. Es überkam mich das gleiche Gefühl wie früher in der Schulbank. Ich versuche es wirklich zu verstehen, und bis zu einem gewissen Punkt klappt es auch, aber dann ist Schluss. Es quält mich dann einfach nur.

  15. Quälen will ich natürlich niemanden. Aber jetzt weißt du, warum Frau Rau mich damals zum Bloggen drängte; davor hatte sie sich das alles von mir anhören müssen statt nur darüber zu lesen.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.