Thomas Kahle
Dieses Mal geht’s wieder etwas in die theoretische Informatik. Ein paar sogenannte Hobbymathematiker*innen haben nämlich BB(5) berechnet, d.h. die maximale Laufzeit einer anhaltenden Turingmaschine mit 5 internen Zuständen.
Was das mit Berechenbarkeit, großen Zahlen und der Goldbachvermutung zu tun hat, bespreche ich hier in der Sommerfolge. Wir müssen nämlich nur noch bis BB(27) vorstoßen, bis wir die Goldbachvermutung algorithmisch lösen können. Kann aber noch dauern, denn BB(5) hat 41 Jahre gedauert.
- Scott Aaronson’s blog post on BB(5)
- The busy beaver frontier (vor Juli 2024)
- π=3 Große Zahlen
- BBchallenge.org
- Tolle interaktive Erklärung der Turingmaschine auf bbchallenge.org
- Hat Turing wirklich das Halteproblem diskutiert?
- LEGO Turingmaschine
- Code Golf
- Rado 1961 Paper On non-computable functions
- Bericht der GI-Konferenz von 1983
- Der fertige formale Coq-Beweis
- Eine 748-state Turingmaschine, die genau dann anhält, wenn ZFC inkonsistent ist.
- BB(5)-Artikel in Quanta Magazine
Feedback gerne auf Mastodon @Eigenraum@podcasts.social, an feedback (bei) eigenpod.de oder in die Kommentarspalte auf der Episodenseite.
Verwandte Folge:
Automatisch generiertes Transkript (nicht geprüft)
6, 3, 6, 0, 7, 6, 0, 8.
Ja, hallo zusammen. Ich begrüße euch. Mein Name ist Thomas Kahle.
Ich bin Mathematiker aus Magdeburg.
Und das hier ist nicht der Cottbuser Postkutschen-Podcast, sondern der Eigenraum.
Ein kleiner, feiner Mathe-Podcast, den ich mache, weil ich denke,
dass es nicht genug Mathe-Podcasts gibt.
Ich wollte jetzt immer noch mal sagen, wer ich eigentlich bin,
weil sonst fange ich ja immer nur an zu quatschen.
Und ich begrüße euch zu meiner kleinen Sommerfolge. Ich bin nicht in meinem
Podcast-Studio, sondern unterwegs. Und deshalb hört sich vielleicht auch alles etwas anders an.
So, die letzte Sommerfolge war Eigenraum 20, hexagonale Spiele,
an die ich noch gute Erinnerungen habe.
Jetzt bin ich bei 39, was mir sagt, dass ich wohl so 19 Folgen in einer Saison,
einer Season gemacht habe.
Aber ihr kennt das ja, mein Senderhythmus ist nicht so regelmäßig.
Also ich fange mal wieder mit einer Geschichte an.
Und die Geschichte, die habe ich schon mal in einem anderen Podcast erzählt.
Und ich dachte, die hätte ich wirklich erlebt. Oder ich wüsste,
dass die wahr war. Aber ich finde wirklich keine Referenzen mehr dafür.
Vielleicht habe ich sie mir auch einfach ausgedacht oder geträumt.
Aber vielleicht findet auch jemand noch Referenzen dafür und kann mir nochmal
einen Link zu einem Video von dieser Geschichte schicken. Und die geht jedenfalls so.
Also es gibt diese amerikanischen Late-Night-Shows, die kennt ihr ja vielleicht,
Conan O'Brien und fing mal an mit David Letterman und Tonight Show und was es da so alles gibt.
Und einer von diesen Hosts da, so ein lustiger Comedian, der hat aber immer
zwei Mathematiker eingeladen und hatte für die die Aufgabe und die waren nicht
darauf vorbereitet, dass sie die größte Zahl, die sie kennen,
auf ein Post-it schreiben sollen.
Also, kennt ihr dieses Spiel noch, die größte Zahl zu sagen?
Also Kindergarten oder Grundschule gab es das bei uns.
Da gab es zwei wichtige Naturkonstanten, die Sternzahl und die Steinzahl.
Und dann konnte man die irgendwie kombinieren. Also zum Beispiel Sternzahl hoch
Steinzahl. Also Sternzahl ist die Anzahl der Sterne und Steinzahl die Anzahl der Steine.
Und naja, aber es war immer ziemlich schwierig festzustellen, wer gewonnen hat.
Und so war es eben auch bei diesem Wettbewerb in dieser Comedy-Show.
Und was da wohl passierte war, irgendwie der Horst hatte glaube ich 9 hoch 9
hoch 9 hoch 9 hoch 9 immer so diagonal über das ganze Post-it geschrieben.
Und einer von den Mathematikern hat geschrieben Graham's Number,
also die Graham-Zahl und der dritte hat geschrieben Busy Beaver von Busy Beaver von 5.
Und darum geht es heute. Graham's Number gab es auch schon mal im eigenen Raum,
nämlich in Folge 17 Lieblingszahlen. Ist nämlich auch so eine Lieblingszahl von mir.
Soll die größte Zahl sein, die
je in einem mathematischen Beweis wirklich genutzt wurde und da vorkam.
Und in meinem alten Podcast Piece genau 3 gibt es auch eine Folge über große
Zahlen. Und die ist vom Juni 2020.
Und die ist mittlerweile veraltet. Es gibt nämlich mathematische News.
Und die haben mit der dritten Antwort zu tun. Busy Beaver von Busy Beaver von
5. Also fünf fleißigen Bibern. Und diese News hier haben schon groß die Runde gemacht.
Also wenn ihr so relevante YouTube-Kanäle oder Instagram-Accounts verfolgt,
habt ihr vielleicht davon schon gehört.
Und in dieser schwierigen Zeit, in der wir uns befinden, manchmal denkt man,
politisch spricht alles zusammen, das Ende der Zivilisation naht.
Da gibt es doch noch gute Nachrichten.
Denn Busy Beaver von fünf ist jetzt bekannt.
Seit sehr kurzem, seit 2. Juli 2024. 24.
Und das Problem bei der Talkshow, die ich eben erwähnt habe,
das war, dass sie gar nicht richtig feststellen konnten, wer gewonnen hatte.
War nicht klar, welche Zahl denn jetzt eigentlich die größte war.
Also diese neun auf der Diagonale, die sind ganz sicher auf Platz drei.
Grahams Number ist aber auch ziemlich groß und Busy Beaver von fünf ist jetzt
bekannt, aber der hatte ja geschrieben, sicherheitshalber Busy Beaver von Busy Beaver von fünf.
Und Busy Beaver von fünf selbst ist auch gar nicht so groß. Also Busy Beaver
ist so eine Funktion, und die kann ich eben aufrufen für fünf.
Deswegen ist Busy Beaver von fünf eine Zahl.
Und dieser wichtige Schritt, den fünften Wert von dieser Busy Beaver-Funktion
auszurechnen, der hat schlappe 41 Jahre gedauert.
So, also worum geht es hier eigentlich?
Oberflächlich ist es erstmal wieder so eine Zahlenfolge, wie wir sie ganz oft haben.
In der OEIS, meiner geliebten Online-Enzyklopädie der Zahlenfolgen, ist es Folge 60.843.
Und wir kennen von dieser Folge genau fünf Werte mittlerweile.
Sie lauten 1, 6, 21, 107, hört sich noch nicht so schlimm an,
wächst dann aber schnell.
47.176.870. Und diesen fünften Wert, den kennen wir eben seit dem 2.
Juli diesen Jahres, 2024.
Und die Veröffentlichung passierte auch nicht in einem wissenschaftlichen Paper,
sondern auf einer Webseite. Auf der Webseite bbchallenge.org.
Das ist so eine Art Citizen Science Webseite, also richtig schick mit Discord
und irgendwelche anonymen Leute machen damit und in der Ankündigung,
schreiben die Autoren dieser fundamentalen Leistung auch, dass sie planen,
innerhalb von nur zwei Jahren noch ein Human-Readable-Paper dazu zu schreiben.
Da fragt man sich, was haben sie denn bisher?
Bisher haben sie einen formalisierten Beweis in der Programmiersprache Coq,
also wie Hahn, und der beweist ihre Aussage. Also dass diese Busy Beaver von 5 zahlt.
Genau das ist diese 47 Millionen, die ich eben gerade erwähnt habe.
Und den kann man jetzt überprüfen. Also das ist richtig so formalisierte Mathematik.
Also man kann auf seinem eigenen Laptop das laufen lassen und nach 10 Stunden sagt er dann, ja stimmt.
Und dann, wenn man dem Laptop traut, dann stimmt das auch.
Aber fangen wir mal am Anfang an. Was für Biber überhaupt? Das Ganze hat mal
wieder mit Informatik zu tun. Ich liebe ja Informatik. Und mit Berechenbarkeit.
Es ist nun mal ein Fakt des Lebens, dass es nicht berechenbare Zahlen gibt und
nicht berechenbare Funktionen und so weiter.
Und Computer sind eben nicht allmächtig. Und die Informatik fing ja mal an als
die Wissenschaft der Berechenbarkeit.
Eben die Computerwissenschaft.
Und das wichtigste Problem mit diesem Bereich ist ja bekanntermaßen das Halteproblem.
Das kann man auch mit folgender Analogie ziemlich einfach verstehen.
Also wenn man zum Beispiel nach dem Weg fragt, irgendwen, und die Anweisung
bekommt, fahr jetzt einfach mal gerade auf dieser Straße runter hier,
dann kommen später so ein paar Stahlbrücken, unter denen fährst du durch und
nach der letzten Brücke fährst du an der nächsten Kreuzung links ab.
So, und wenn du jetzt ein Computer bist oder wie ein Computer denkst,
dann kannst du mit der Anweisung nicht so viel anfangen, weil du eben nicht
feststellen kannst, bist du
schon an der letzten Brücke oder bist du noch nicht an der letzten Brücke.
Oder du musst halt erstmal die ganze Straße bis zum Ende fahren und dann nochmal
zurück. Aber was ist, wenn die Straße unendlich lang ist, so wie die natürlichen Zahlen?
Also nachdem du alle Brücken gesehen hast, könntest du das entscheiden,
aber du weißt nie, ob du alle Brücken gesehen hast. Und das ist in der Essenz das Halteproblem.
Formalisiert wird das so, das Halteproblem ist es, ein Computerprogramm zu schreiben.
Was als Eingabe ein anderes Computerprogramm bekommt und dann ausrechnet,
ob das ein gegebenes Programm anhält oder eine Endlosschleife macht.
Und so ein Testprogramm kann man nicht schreiben.
Also man kann nicht eins schreiben, was alle anderen Computerprogramme untersuchen
kann. Das gleiche Programm soll alle Programme untersuchen.
Das führt im Wesentlichen zu so einer Paradoxie. Also man könnte sich zum Beispiel
mal fragen, was passiert, wenn man dann dieses Programm, was alle anderen Computerprogramme
untersucht, in sich selbst einsetzt.
Und mit solchen Paradoxien hat Alan Turing in den 1930er Jahren untersucht,
was die Grenzen der Berechenbarkeit sind, obwohl es heutzutage eigentlich nicht
mehr so ganz klar ist, ob er das Halteproblem damals schon betrachtet hat.
Ich verlinke euch da mal ein Paper, was am 30.06.
Dieses Jahres gepostet wurde von Joel David Hamkins, einem Logiker und Philosophen,
der sich damit auseinandergesetzt hat.
Also das ist jetzt im Prinzip noch Gegenstand der informatikgeschichtlichen Forschung.
Also die Formalisierung von Computerprogrammen ist ja bekanntermaßen die Turing-Maschine.
Also allgemeine Computerprogramme zu untersuchen ist zu kompliziert,
weil Computer kompliziert sind.
Also macht man so einen idealisierten Computer, der im Wesentlichen alles kann,
was unser moderner Computer auch kann und viel einfacher zu untersuchen ist.
Und dieser idealisierte Computer, der besteht aus einem Speicher,
wie jeder Computer auch einen Speicher hat.
Der Speicher ist einfach so ein unendlich langes Band, vielleicht in beide Richtungen,
auf das man Nullen und Einsen schreiben kann.
Also der hat genauso Bits als Speicher, aber eben unendlich viel und das ist
in so einem Band organisiert.
Es gibt eine erste Position, zweite Position, dritte Position und sagen wir
für jede natürliche oder ganze Zahl eine Position.
Und außerdem hat diese Turing-Maschine einen Kopf, der befindet sich an einer
Position dieses Bandes und entscheidet jetzt mittels sogenannter Zustandsübergänge, was er macht.
Und zwar geht es immer so, der Kopf, der ist in einem Zustand und von diesen
Zuständen gibt es nur endlich viele.
Und dann liest er, was da gerade auf dem Band steht, wo er ist und abhängig
von diesen zwei Sachen, in welchem Zustand bin ich und was habe ich gerade gelesen,
schreibt der Kopf etwas aufs Band und geht dann nach links oder rechts und wechselt
potenziell in einen anderen Zustand.
Und dann ist er woanders und kann da weitermachen.
Und dann läuft das Ganze und dann gibt es irgendwie einen speziellen Zustand,
der heißt Halt, das ist dann das Ende des Programms.
Also wenn zum Beispiel signalisiert werden soll, dass irgendeine Berechnung
jetzt erfolgreich durchgeführt wurde.
Und bei der Untersuchung der Komplexität von Algorithmen und auch der Berechenbarkeit
hat es sich jetzt als günstig herausgestellt, und das war deutlich nach Turing,
die Anzahl dieser internen Zustände zu begrenzen.
Also die Turing-Maschinen zu unterteilen in Familien, je nachdem wie viele von
diesen internen Zuständen man haben kann.
Das ist ein bisschen so wie bei dieser Sportart Code Golf, bei der man versucht
mit möglichst wenig Anschlägen, also mit möglichst wenig Programmcode ein gegebenes Problem zu lösen.
Also ist es so eine Art Turing-Code-Golf, zu sagen, man will ein Problem lösen,
aber mit einer Turing-Maschine, die nur eine begrenzte Anzahl von internen Zuständen hat.
Und so eine Programmierung, so eine Turing-Maschine, genau wie bei einem echten
Python-Programm oder so, die kann jetzt eine Endlosschleife enthalten.
Zum Beispiel könnte die Turing-Maschine einfach immer nur, geh links,
geh rechts, mit deinem Kopf, geh links, geh rechts, schreibe nichts auf das
Band oder schreibe genau das auf das Band, was du da gelesen hast.
Und dann hat man einfach eine Endlosschleife, weil es nie in diesen Zustand Halt wechselt.
Oder die kann dann eine Berechnung ausführen und dann in den Haltzustand wechseln
und dann steht zum Beispiel das Ergebnis der Berechnung in irgendeiner binären Kodierung auf dem Band.
So, und die Programmierung besteht jetzt darin, also ein Programm für eine Turing-Maschine
zu schreiben, diese Übergänge zu definieren.
Was passiert in welchem Zustand, wenn was gelesen wird?
Hier wird es gleich wichtig, Turing-Code-Golf zu spielen, also mit möglichst
wenigen Zuständen auszukommen.
Also egal, ob es nun Turing war oder jemand anders, der das Halteproblem analysiert
hat, die Turing-Maschine ist für die Entwicklung der Informatik ein super Durchbruch,
denn so ein einfaches Modell kann man total gut untersuchen.
Und trotzdem ist es im Prinzip äquivalent zu einem MacBook, bei dem eigentlich
nur Apple weiß, was genau da drin passiert.
Aber die Turing-Maschine ist sozusagen Open-Hardware und jeder und jeder kann sie studieren.
So, jetzt kommen wir zum Beaver. Wenn so eine Turing-Maschine mit einer beschränkten
Anzahl von Zuständen ausgestattet ist, dann ist die Programmierung eventuell
nicht sehr flexibel, dann kann man damit eventuell nicht sehr viel machen.
Denn die Zustände bestimmen ja, was in jedem Schritt passiert.
Und sagen wir mal, wir haben nur einen Zustand, damit die Maschine überhaupt
anhält, muss dieser Zustand Halt sein.
Also was kann die Maschine machen aus dem Startzustand? Entweder eine Eins schreiben
oder nicht und dann anhalten im nächsten Zustand.
Und so kann man sich halt fragen, und das machte 1961 Tibor Rado,
ein ungarischer Mathematiker, der Mathematik übrigens im Gefangenenlager des
Ersten Weltkriegs in Sibirien gelernt hat.
Möglichst komplizierte Programmierprobleme auszudrücken mit möglichst einfachen
Turing-Maschinenprogrammen.
Also echtes CodeGolf wäre jetzt, ihr habt nur 44 Zeichen Python-Code zur Verfügung,
ihr wollt die ersten 100 Katalan-Zahlen ausgeben und Turing-Maschinen-CodeGolf
ist, ihr habt nur eine fixierte Anzahl, sagen wir 5 Zustände und wollt irgendwas
lösen, zum Beispiel möglichst viele Zahlen auszugeben. Und noch anhaltend.
Also was ist jetzt das einfachste Maß für ein kompliziertes Problem?
Da entschied sich Rado dafür, was ist die maximale Anzahl Einsen,
die ihr aufs Band schreiben könnt?
Also ihr habt eine Maschine, ihr dürft die programmieren, aber ihr dürft nur
N von diesen internen Zuständen benutzen.
Und was ist die maximale Anzahl an Einzen, die ihr damit aufs Band schreiben könnt?
Und noch anhaltend, und das nannte er die Busy Beaver-Funktion und den Busy Beaver-Wettbewerb.
Die Leute sollten ihre beste Touring-Maschine mit drei Zuständen einschicken
und nachweisen, wie viele Einzen so eine Touring-Maschine aufs Band schreiben
kann. Und der Rekord war übrigens sechs.
Und das ist das International Busy Beaver Game und der Rekord war sechs.
Aber niemand konnte zeigen, dass es auch das Maximum war. Deswegen macht er ein Spiel daraus.
Also es waren Programme, Maschinen bekannt, die sechs Einzelnen ausgeben konnten,
aber keine, die mehr ausgeben konnten.
Und ein paar Jahre später gelang es aber zu zeigen, dass sechs auch tatsächlich das Maximum ist.
Dazu reduziert man erst mit der Anzahl der Symmetrien die Maschinen,
die man überhaupt betrachten muss.
Es gibt übrigens 16.777.216 Turing-Maschinen mit drei internen Zuständen.
Und mit Symmetrie kann man die auf 82.944 reduzieren. Und die muss man dann aber alle prüfen.
Und einem Doktoranden von RADO namens Lin gelang es, 82.904,
also alle bis auf 40, mit einem speziellen Computerprogramm zu entscheiden.
Also ein spezielles Computerprogramm, was als Eingabe ein anderes Computerprogramm
bekämpft und entscheidet, ob das Programm anhält oder nicht.
Das ist nämlich der entscheidende Punkt hier.
Und das ist aber möglich, weil hier ja nicht alle Programme untersucht werden
sollen, wie beim Halteproblem, sondern nur diese speziellen drei Zustands-Turing-Maschinen.
40 blieben trotzdem über, die er dann alle per Hand nachprüfte.
Das ist so ein Fall, wo ich vielleicht verzweifelt wäre.
40 Fälle, da denkt man sich, da muss ich noch ein bisschen mehr nachdenken.
Aber es gibt auch Leute, die sagen, 40 Fälle, kein Problem. Schauen wir uns die mal alle per Hand an.
Also galt die maximale Anzahl von Einsen, die so eine Drei-Zustand-Storing-Maschine
aufs Band schreiben kann, ist 6.
In diesem ersten Paper, in dem man den Wettbewerb vorschlägt,
zeigt er auch, dass die Zahl dieser Einzelnen, die maximal geschrieben werden
können, in Abhängigkeit von der Anzahl Zustände immer endlich sein muss.
Das ist auch nicht schwer, denn es gibt nur endlich viele Turing-Maschinen mit
diesen vorgegebenen Anzahlzuständen, mit N Zuständen.
Also sind darunter nur endlich viele, die anhalten und jede von denen schreibt
irgendeine Anzahl von Einzelnen aufs Band und das Maximum über diese endliche
Menge ist eben diese Funktion.
An dieser Stelle muss man jetzt nochmal etwas genauer sein. Die Folge 1,
6, 21, 147, 147 Millionen, 176.870, die jetzt in OEIS steht,
die enthält zwar eine 6, aber wenn ihr gerade aufgepasst habt,
nicht an der dritten Stelle, sondern an der zweiten.
Und das liegt daran, dass man heutzutage nicht mehr so sehr die Anzahl der Einsen
betrachtet, sondern einfach zählt, wie lange die Maschine läuft.
Also wie lange kann so eine Turing-Maschine laufen? wie viele Schritte macht
sie, wenn sie nur n interne Zustände hat und noch anhalten soll.
Natürlich kann ich auch Programme schreiben, die Endlosschleifen haben, ganz einfach.
Aber wenn sie noch anhalten soll, dann ist die maximale Anzahl Schritte begrenzt.
Und das ist die Zahl, die jetzt gefunden wurde für fünf interne Zustände.
Und das nennen wir das, was ich jetzt Busy Beaver von fünf nenne.
Die Anzahl der Einsen, die maximal geschrieben werden können mit fünf Zuständen,
ist, wenn ich das jetzt richtig sehe, noch nicht bekannt, beträgt aber mindestens 4098.
Okay. Ihr könnt es ja auch mal für Python, Haskell, Brainfuck oder was auch
immer eure Lieblingsprogrammiersprache ist, überlegen, wie schafft ihr es,
ein Programm zu schreiben, das keine Endschlussschleife enthält,
nur 44 Zeichen lang ist, aber möglichst lange läuft oder möglichst viel Zeug ausgibt?
Und vor allem, wie beweist ihr, dass euer Programm optimal ist?
Also ihr könnt es natürlich so als Wettbewerb spielen. Okay,
ihr habt 44 sich Zeichen zur Verfügung in Haskell und wie schreibt ihr ein Programm,
das möglichst lange läuft damit?
Aber könnt ihr auch beweisen, dass euer Programm das Optimum ist?
Oder wie kann man das Optimum finden?
Und das ist eben für Python sicher nicht einfach, dass es eben eine komplizierte
Programmiersprache ist und deswegen untersuchen wir eben diese Turing-Maschinen.
Denn die sind einfach und irgendwas muss man ja machen.
Die Suche nach Busy Beaver von 4 und dann später 5 war schon immer ein Wettbewerb.
Also dieses ganze Thema hat immer
seinen Wettbewerbscharakter bei so einer Informatik-Theorie-Konferenz
der Gesellschaft für Informatik, der Fachgesellschaft für Informatik in Deutschland.
1983 in Dortmund gab es auch mal so ein Zusammentreffen aller Spieler und Spielerinnen.
Ich verlinke euch mal den Bericht von dieser GI-Konferenz. Also klickt mal auf
diesen Link GI-Konferenz. Der ist wirklich Recommended Reading.
Also wenn man da mehr verstehen will. Da stehen zum Beispiel die drei Gründe
für diesen Busy Beaver Wettbewerb drin.
Und die lauten, man will das Problem weiter untersuchen. Man will weitere interessante
Beispiele in der Komplexitätstheorie erhalten.
Und, das kann ich jetzt nicht übersetzen, Encourage the Desire to Play.
Also Förderung des Spieltriebs. Förderung des Spieltriebs ist auch ein Grund,
warum es das Busy Beaver Spiel gibt.
Und es gibt dann auch ein Kapitel, in dem verschiedene Arten von Maschinen charakterisiert
werden. Da zitiere ich auch mal auf Englisch.
Anything, moving on the tape and changing his state. Also da wird so ein bisschen
Typologie oder Zoologie von solchen Turing-Maschinen gemacht.
Und eine ist halt sozusagen Beamter.
Und der Beamte schert sich am meisten um seinen eigenen Fortschritt,
produziert aber überhaupt keine Einsen.
Also da wird unterschieden, wie viele Einsen die Biber schreiben,
die lange laufen. Und so.
Der Geist dieses Dokuments, der lebt bis heute weiter und zwar in dieser Webseite,
die ich am Anfang schon erwähnte, bbchallenge.org, busybeaverchallenge.org und
diese Webseite startet aber erst 2022 und ist jetzt schon am Ziel.
Also das Ziel war, einen Busy Beaver von 5 zu bestimmen. Das war eben offen bis zum 2.
Juli und Busy Beaver von 4 wurde vor 41 Jahren gefunden. Und ein Teil dieses
Erfolgs ist, glaube ich, auch einfach die Coolness dieses Projekts und des Gründers Tristan Sterin.
Das ist die gleiche Coolness wie von Jakob Trevnik aus Eigenraum Folge 7,
der diese selbstplottende Formel verbessert hat zu einer selbstrendernden Formel.
Und das sind so Leute, wenn man sich anschaut, was die machen,
sieht man einfach, ja, so sollte das gemacht werden.
Und wenn man Leute sieht, die etwas verfolgen, so wie es gemacht werden sollte,
damit es richtig ist, dann machen auch Leute mit.
Dann füllt sich der Discord und es wird ein großer Erfolg. Und deswegen ist
vielleicht das so schnell gegangen.
Und er popularisierte auch die sogenannten State Diagrams. Also wer zelluläre
Automaten mag, der kann sich auch von diesen Busy Beavern die State Diagrams anschauen.
Das ist einfach nur so ein Diagramm, wo in jeder Zeile ein Zustand des Bands geschrieben ist.
Und das soll ja möglichst viele Einsen schreiben oder möglichst lange laufen.
Und dann malt man die so untereinander und sieht man auch interessante Muster,
die da entstehen, wie bei diesen populären Diagrammen von zellulären Automaten.
So, und am 2. Juli haben sie jetzt sich siegreich erkehrt im Kampf um den fleißigsten
Beaver. Die Beweismethode ist immer noch die gleiche wie bei Busy Beaver von drei.
Also die fleißigsten Beaver oder der fleißigste Beaver, die Turing Maschine,
die am meisten einzeln schreibt, ach ne, die die am längsten läuft, war schon bekannt.
Also der Rekord, der bekannt war, ist der tatsächliche Maximalwert.
Aber es mussten eben noch viele andere Turing Maschinen ausgeschlossen werden.
Also Maschinen, die länger laufen.
Die aber nicht angehalten haben. Und für die muss man jetzt beweisen,
dass sie niemals anhalten werden. Und das ist das Brückenproblem.
Also das ist jetzt das Problem. Ich habe jetzt eine Turing-Maschine,
die läuft länger als diese 47 Millionen und die hält einfach nicht an.
Und jetzt muss ich irgendwie einen Beweis finden, dass diese Turing-Maschine niemals anhält.
Dass da immer noch Brücken kommen und ich nie links abbiegen kann.
Und dazu wurden eben solche Decider geschrieben, andere Computerprogramme,
die die einzelnen Biber untersuchen. Und jetzt kommt der Citizen-Science-Aspekt.
Ins Spiel, dass das eben dezentral von einer Community übernommen wurde.
Und da sind eben auch anonyme Contributions dabei.
Also die Leute formalisieren mit Hilfe von gewissen Techniken in diesem Beweisprogramm
COG die Programme, die entscheiden oder zeigen, dass diese langlaufenden Turing-Maschinen
nicht mehr anhalten werden.
Und das ist eben Einzelarbeit. Das Halteproblem hat allgemein keine Lösung,
aber man kann eben nach diesen speziellen Programmen suchen,
die spezielle Programme untersuchen.
Und ja, so konnte man dann nach und nach zeigen, dass all diese anderen Turing-Maschinen
niemals anhalten werden und damit der Rekord, der bekannt war von,
jetzt habe ich es schon wieder vergessen, 47 Millionen irgendwas,
tatsächlich die längste Laufzeit ist für eine Turing-Maschine mit fünf internen Zuständen.
So, was bleibt noch? Busy Beaver von 6?
Tja, das scheint sehr weit entfernt zu sein.
Aber bevor ich noch was dazu sage, können wir uns den Rekordhalter von Busy
Beaver von 5 nochmal anschauen.
Ein Rekordhalter ist die sogenannte Markson-Bantrock-Turing-Machine.
Also wie schreibt man so eine Turing-Maschine überhaupt?
Also es ist eigentlich nur eine kleine 5-Kreuz-2-Matrix, die sagt,
was in jedem der fünf Zustände, also sagen wir mal die fünf Zeilen,
passieren soll, wenn eine 0 Grad gelesen wird und passieren soll,
wenn eine 1 Grad gelesen wird.
Und jeder Eintrag von der Matrix sagt dann, was soll aufs Band geschrieben werden,
soll der Kopf sich nach rechts oder links bewegen und in welchem Zustand soll
danach gewechselt werden.
Und das ist dann so eine kleine Tabelle, da steht dann immer so kurz drin 1RB
und das heißt, schreibe eine 1, gehe nach rechts und wechsle in Zustand B.
Und wenn man im Zustand E ist und eine 0 liest, dann hält das Programm eben an.
Aber was macht die Maschine? Wie findet man sie? Kann man irgendwie verstehen,
warum die so fleißig ist?
Und in der Tat berechnet die eine ganz komische rekursive Funktion.
Also die nimmt eine Eingabe, eine Zahl, die auf dem Band kodiert ist und berechnet
fünf Mal die Zahl plus 18 durch 3, wenn die Zahl durch 3 teilbar ist.
Fünf Mal die Zahl plus plus 22 durch 3, wenn die Zahl Rest 1 Modulo 3 liefert
und hält an, wenn die Zahl Rest 2 Modulo 3 liefert.
Und jetzt berechnet die die Folge, die mit 0 anfängt von dieser Zahl.
Und die geht so 0, 6, 16, 34, Punkt, Punkt, Punkt, Punkt, Punkt und dann so
ungefähr, ich zähle mal durch, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, ungefähr 12 Zahlen, dann kommt sie zu 12.284 und hält dann an.
Aber eben dauert es bei dieser Turing-Maschine ziemlich lange,
weil jede Berechnung mittels dieser ganz simplen Programmierung mit Händen auf
dem Rücken implementiert werden muss, wo die fünf Zustände benutzt werden.
Also es ist nicht ein Schritt, so einen Rest auszuwerten. Deswegen sind es eben 47 Millionen Schritte.
Und das erinnert doch irgendwie an diese Kollatz-Vermutung, oder?
Die nennt man doch auch die 3n plus 1-Vermutung. Das ist so ein kleiner Algorithmus.
Da geht immer eine Zahl rein, auf die dann iterativ immer eine ganz einfache
Vorschrift angewendet wird.
Nämlich wenn die Zahl durch 2 teilbar ist, dann macht man das auch und wenn
die Zahl nicht durch 2 teilbar ist, dann nimmt man dreimal die Zahl plus 1 und
damit bildet man so Folgen und empirisch ist es so, dass egal wo man anfängt,
diese Folgen immer bei 1 enden.
Also jede Zahl, die man da reinsteckt, wenn man diesen kleinen Algorithmus ausführt,
wenn die Zahl gerade ist, durch 2 teilen, wenn die Zahl ungerade ist,
dreimal die Zahl plus 1 nehmen, endet irgendwann bei 1. Und.
Und niemand kann das beweisen. Und diese Busy Beaver, die sind so ähnlich.
Die berechnen den Rest Modulo 3 und bilden dann eine komische Vorschrift. Okay.
Und wenn man diese Idee weiter verfolgt, dann kommt man auf die Idee,
mit Busy Beaver Mathematik zu untersuchen.
Das ist eigentlich schon eine ziemlich ältere Idee. Die gibt es schon seit den 1990er Jahren.
Beispielsweise wurde mal gezeigt, dass es eine 27-Zustand-Turing-Maschine gibt,
die genau dann anhält, wenn die Goldbach-Vermutung falsch ist.
Das ist so eine zahlentheoretische Vermutung, die sagt, dass jede gerade Zahl,
die größer als 2 sich als Summe von 2 Primzahlen schreiben lässt,
widersteht allen Beweisvermutungen und auch der Suche nach einem Gegenbeispiel.
Aber es gibt eben diese 27-Zustands-Turing-Maschine, die genau dann anhält,
wenn es ein Gegenbeispiel gibt.
Und es gibt auch eine 744-Zustands-Turing-Maschine, die genau dann anhält,
wenn die Riemann-Hypothese falsch ist. Und es gibt auch eine 748-Zustandsmaschine,
die genau dann enthält, wenn die Zermelo-Frenkel-Choice-Mengenlehre widersprüchlich ist.
Also die Mathematik widersprüchlich ist. Ich verlinke euch mal einen Turing-Maschinen-Simulator,
wo die implementiert ist. Der läuft direkt im Browser.
Also ich habe da so einen Tab offen und bisher läuft sie noch.
Hat kein Gegenbeispiel zur Zermelo-Frenkel-Mengenlehre gefunden.
Das heißt aber, diese Dinge kann man überprüfen.
Nehmen wir mal die Goldbach-Vermutung. Wenn man jetzt Busy Beaver von 27 kennen würde,
dann weiß man, wie lange man diese Goldbach-Maschine laufen lassen muss und
wenn sie länger läuft, dann wird sie nie mehr anhalten, weil keine Maschine,
die anhält und 27 Zustände hat, so lange laufen kann.
Wenn sie länger läuft, wird sie nicht mehr anhalten. Das heißt,
die Goldbach-Vermutung stimmt.
Leider, leider ist aber Busy Beaver von 27 ziemlich groß und Busy Beaver von
744 noch größer und Busy Beaver von 748 noch größer und unbekannt.
Und außerdem ist seit Gödel klar, dass man in der Zermelo-Frenkel-Mengenlehre
nicht zeigen kann, dass die Zermelo-Frenkel-Mengenlehre widerspruchsfrei ist.
Daraus folgt dann auch, dass Busy Beaver von 47 auf jeden Fall eine nicht berechenbare Zahl ist.
Also eine Turing Maschine kann nicht entscheiden, wie lange man da laufen muss,
kann nicht berechnen, wie lange man laufen muss, um das Gegenbeispiel zu finden.
Aber jedenfalls für die Quizshow vom Anfang wissen wir jetzt wenigstens,
dass Busy Beaver von Busy Beaver von 5 ist Busy Beaver von 47 176 870.
Aber irgendwie denkt man da doch, dass Busy Beaver von 6 oder 7 vielleicht die
nächsten Ziele für die BB-Challenge sein sollten.
Pavel Kropitz entdeckte übrigens vor einigen Jahren, dass Busy Beaver von 6
mindestens 10 hoch, 10 hoch, 10 hoch, 10 hoch, 10 hoch, 10 hoch,
10 hoch, 10 hoch, 10 hoch, 10 hoch, 10 hoch, 15 Mal wiederholt ist.
Also so ein Potenzturm mit 10, der Höhe 15 hat.
Also schon mal eine ziemlich große Zahl. Offensichtlich hat Kruppels diese sechs
Zustands-Turing-Maschine, die er dafür, also für diese untere Schranke konstruiert
hat, nicht tatsächlich für diese Anzahl von Schritten ausgeführt werden.
Diese Potenztürme, die wachsen wirklich extrem schnell, wie ihr vielleicht aus
der Folge große Zahlen oder Studium der Graham-Zahl euch erinnert.
Stattdessen hat er verstanden, was die Maschine tat und es stellte sich heraus,
dass sie so einen iterativen Prozess anwendet, wie oben mit der Funktion,
die der Busy Beaver von 5 Algorithmus berechnet.
Also State of the Art bei der Untersuchung von solchen fleißigen Beavern ist
es, solche iterativen Funktionen ähnlich der Kollatzvermutung zu untersuchen.
Und deswegen ist auch, weil die Kollatzvermutung so einen, ja,
diesen Anschein hat, als ob sie irgendwie ganz neue Mathematik benötigt,
strahlt es auch ein bisschen auf diese Busy Beaver-Funktion aus und es fasziniert
einfach viel Mathematikerinnen und Mathematiker.
Ja, und es kommt uns natürlich völlig unrealistisch vor, Busy Beaver von 6 zu
bestimmen, aber wer weiß, was wir noch für Mathematik entdecken und erfinden,
ob wir irgendwann die Kollatzvermutung verstehen und dann auch Busy Beaver von
6 oder 7 oder so zumindest verstehen.
Busy Beaver von 5 kam uns auch völlig hoffnungslos vor, vor 40 Jahren.
So, also warum machen wir das? Ich entlasse euch ich jetzt mal mit einer Antwort
auf das Warum, die Scott Aronson gegeben hat, einer der Leute,
die aktiv sind in diesem Bereich.
Er sagte, der Kosmos ist so unermesslich und.
Mit solchen Dingen wie Busy Beaver von 5 zu berechnen, können wir unseren Fortschritt messen.
Busy Beaver gibt irgendwie eine Messlatte, wie weit wir sind in unserem Verständnis.
Weil einfach nur eine weitere Zahl zu berechnen, das ist kein Prozess,
der in festgelegten Schrittlängen vor sich geht.
Denn für jede weitere Zahl ist eine unglaubliche Menge von neuer Kreativität
und neuer Mathematik nötig.
Also tun wir es, um zu sehen, dass wir noch nicht stehen geblieben sind.
Und wahrscheinlich gibt es für Busy Beaver 5 keinen Nobelpreis und keine Fields-Medaille,
denn es ist eben ein Community-Projekt und manche der Teilnehmenden sind anonym.
Man kann bei denen vielleicht nicht mal feststellen, ob sie die Altersgrenze
für die Fields-Medaille erfüllen.
Also es bleibt jetzt wahrscheinlich erstmal nicht spannend. Ich würde jetzt
gerade gerne sagen, es bleibt spannend, aber bevor bei Busy Beaver von 6 wirklich
was passiert, könnten einige von uns schon das Zeitliche gesegnet haben.
Aber es gibt ja noch viel andere interessante Mathematik, mit der man sich beschäftigen kann.
So, das war es mit meiner kleinen, bieberigen, tierischen Sommerfolge hier.
Ich danke euch fürs Zuhören. Wenn es euch gefallen hat, wie immer,
empfehlt den Podcast weiter, Folgt, liked und sternet auf allen sozialen Netzwerken,
in der Podcast-App eurer Wahl, auf YouTube, wo auch immer ihr die Glocke abonnieren könnt.
Ich bin at eigenraum at podcasts.social bzw.
At eigenpod auf Instagram und Threads.
Und meine Lieblingsplattform ist und bleibt Mastodon. Also folgt mir da und
bekommt immer die neuesten lustigen kleinen Ideen.
Macht's gut und bis bald. Vielen Dank.