Northstar hat geschrieben:
Habe gerade einen Artikel über die "Graham-Zahl" gelesen.
Die kommt in einem Beweis der Ramsey-Theorie vor und gibt eine obere Schranke an.
Kannst Du eine Quelle angeben? Nur aus Interesse...
Um genau zu sein ist die Grahamzahl G:
3 -> 3 -> 64 -> 2 < G < 3 -> 3 -> 65 -> 2
2 -> 4 -> 3 ist bspw. eine Abkürzung für 2^^^4, wobei ^ hier die Knuth-Pfeile sind.
2^^^4 ist seinerseits soviel, wie 2^^65536.
Und 2^^65536 ist soviel, wie 2^2^2^2.... (65536 mal) ...2^2, eine Zahl, größer, als alles vorstellbare.
Nun ist G (was ja größer ist als 3 -> 3 -> 64 -> 2) noch ne Ecke größer...
(Dem geneigten Leser sei
Wikipedia empfohlen.)
Am schnellsten wächst aber die "Fleißige Biber"-Funktion:
Die Bestimmung der fleißigen Biber ist ein Problem, das nicht allgemein algorithmisch lösbar ist. So ist nicht generell entscheidbar, ob eine gegebene Turingmaschine mit n Zuständen tatsächlich eine Kette von Einsen maximaler Länge schreibt (siehe Entscheidbarkeit). Für einzelne Turingmaschinen geringer Komplexität ist das allerdings möglich. Also ist die Menge der Werte von Σ(n) weder entscheidbar, noch rekursiv aufzählbar, obwohl Σ(n) wohldefiniert ist. Da auch das Komplement dieser Menge nicht rekursiv aufzählbar ist, wird diese Menge gerne als Beispiel für eine Sprache gewählt, die nicht in der ersten Stufe der arithmetischen Hierarchie liegt.
Wegen dieser Eigenschaften der Wertemenge ist die Funktion Σ nicht berechenbar. Man kann außerdem zeigen, dass ihr asymptotisches Wachstum stärker ist als das jeder berechenbaren Funktion.
In der Praxis hat sich gezeigt, dass schon für n > 5 eine Erkenntnis über den Wert Σ(n) realistisch gesehen nicht mehr möglich zu sein scheint. Dazu müsste man für jede einzelne Turingmaschine mit n Zuständen jeweils herausfinden, nach wievielen Schritten sie hält, oder anderenfalls beweisen, dass sie das nicht tut. Aus Gödels Unvollständigkeitssatz folgt direkt, dass nicht für alle solche Turingmaschinen ein entsprechender Beweis existiert. Ob bereits für n = 5 eine solche Erkenntnislücke vorliegt, ist bislang nicht bekannt. Durch die Untersuchung bestimmter Eigenschaften konnten inzwischen zumindest bis auf 40 Maschinen, die kein reguläres Verhalten zeigen[1], eine Unterteilung in haltende Maschinen, die höchstens 4098 Einsen schreiben und nicht haltenden Maschinen unternommen werden. (aus
Wikipedia)
Ein Monster!