Monat: März 2009

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:
  3⁴ 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:
  ⁴3 ist nichts anderes als 3³³³ (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: ³³³3. Aber spätestens jetzt wird es mit der Schreibung und eventueller Klammersetzung extrem verwirrend.

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

• 3⁽¹⁾4 ist 3+4=7, also die Addition, die unterste Ebene, wie oben.
• 3⁽²⁾4 ist 3*4=12, die Multiplikation, eine Ebene drüber.
• 3⁽³⁾4 ist 3⁴=81, die Potenzierung, die nächste Rechenoperation.
• 3⁽⁴⁾4 ist ⁴3=3^{7625597484987} (der Rechner versagt), die Tetration.
• 3⁽⁵⁾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⁽²⁰⁾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⁽³⁾4, also 3⁴.
• 3↑↑4 ist dasselbe wie 3⁽⁴⁾4, also ⁴3. Man kann 3↑↑4 auch schreiben als 3↑3↑3↑3. Das ist die riesige Zahl von oben.
• 3↑↑↑4 ist dasselbe wie 3⁽⁵⁾4, auch zu schreiben als 3↑↑3↑↑3↑↑3.
• 3↑↑↑↑4 ist dasselbe wie 3⁽⁶⁾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⁽ⁿ⁾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) = a^b (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) = 2⁶⁵⁵³⁶-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,2⁶⁵⁵³⁶− 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×10¹⁴³⁹mal.

(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:

(Quelle: Wikipedia, Autor: N.Manytchkine, unter CC AT-SA 2.5 und weiteren Lizenzen) 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:

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