Große Zahlen und fleißige Bieber

1, 2, 1 Million, 1 Trillion, 1 Vigintillion, 1 Googolplex, 1 Googolplex + 1, usw … das Spiel „nenne die größte Zahl“ kann man beliebig fortsetzen. Ein ziemlich geiler Artikel über große Zahlen findet sich hier und hat mich die letzten paar Minuten beschäftigt. Gute Lektüre und jetzt weiß ich endlich was ich auf so einen Zettel (nenne die größte Zahl, die dir einfällt) schreiben würde. Aber was jetzt noch weiß … fleißige Bieber Zahlen sind arschensriesig! So riesig, dass ich für die Erklärung ein Zitat brauche:

His idea was simple. Just as we can classify words by how many letters they contain, we can classify Turing machines by how many rules they have in the tape head. Some machines have only one rule, others have two rules, still others have three rules, and so on. But for each fixed whole number N, just as there are only finitely many words with N letters, so too are there only finitely many machines with N rules. Among these machines, some halt and others run forever when started on a blank tape. Of the ones that halt, asked Rado, what’s the maximum number of steps that any machine takes before it halts? (Actually, Rado asked mainly about the maximum number of symbols any machine can write on the tape before halting. But the maximum number of steps, which Rado called S(n), has the same basic properties and is easier to reason about.)

Rado called this maximum the Nth „Busy Beaver“ number. (Ah yes, the early 1960’s were a more innocent age.) He visualized each Turing machine as a beaver bustling busily along the tape, writing and erasing symbols. The challenge, then, is to find the busiest beaver with exactly N rules, albeit not an infinitely busy one. We can interpret this challenge as one of finding the „most complicated“ computer program N bits long: the one that does the most amount of stuff, but not an infinite amount.

Die Zahlen werden scheinbar schnell sehr groß … zu schnell. 1, 6, 21, 107 und die fünfte kennt man noch gar nicht (ist aber mindestens 47176870), die sechste Zahl ist schon astronomisch. Tjo … Anwendungsbeispiele? Wenn ich den Artikel richtig verstanden habe könnte man damit einige Probleme lösen. Denn eine Turingmaschine kann ja praktisch alles, außer feststellen ob sie anhält oder nicht. Wenn man jetzt also ein Problem mit nur 4 Befehlen auf so einem Band formulieren würde, dann wüsste man nach 107 Schritten, ob das Problem eine Lösung hat (Programm hält) oder nicht (Programm läuft unendlich lange weiter). Ziemlich praktisch. Jetzt bräuchte man eben nur die weiteren Bieberzahlen und könnte so einige wirklich harte Nüsse knacken … zumindest theoretisch, denn schon die sechste Zahl ist zu groß um eine Turingmaschine wirklich so lange laufen zu lassen nur um das als Beweis für irgendwas zu verwenden.

So habe ich es verstanden und dass es arschensriesige Zahlen sind um die er hier geht und sie die Zahlen der Ackermannfunktion locker in die Tasche stecken. Deshalb steht auf meinem Zettel BB(999999999999) … und ja, ich erwarte jetzt Kommentare mit noch größeren Zahlen und ohne auf „deins +1“ oder Unendlichkeiten zurückzugreifen! Go!