Math
Die Turingmaschine und die fleißigen Biber
Ein Papierband zwischen zwei Spulen, ein Metallkopf mit Zustandslampe und eine Regeltabelle. Jeder Schritt läuft als Lesen, Schreiben, Bewegen, neuer Zustand ab; das Journal darunter hält den ganzen Lauf, und eine geänderte Regel bewahrt den alten Lauf als Geist. Die Rekorde sind durch Aufzählen aller Maschinen gefunden, nicht zitiert.
Was passiert
Eine so kleine Maschine ist eine Tabelle und sonst nichts: für jeden Zustand und jedes Symbol, was zu schreiben ist, wohin der Kopf geht, welcher Zustand folgt - oder Halt. Auf dem Tisch ist sie ein Apparat: ein Papierband zwischen zwei Spulen, ein Kopf auf Schienen mit einer Lampe, die seinen Zustand zeigt. Jeder Schritt wird in vier Phasen gespielt - der Kopf liest die Zelle, stempelt die neue Ziffer, rückt eine Zelle weiter, die Lampe wechselt die Farbe -, und das Blatt darunter führt das Journal: jeder Schritt des Laufs als Wärmekarte mit Zeitachse. Ein Klick auf einen Schritt hält die Maschine dort an. Ein Klick auf eine Marke der Tabelle ändert eine Regel: der Lauf vor der Änderung bleibt als gläserner Geist neben dem neuen, mit dem Schritt, an dem sich beide Geschichten trennen. Der fleißige Biber fragt, wie lange eine solche Maschine laufen kann, bevor sie hält. Die Rekorde hier sind nicht zitiert: alle 64 Maschinen mit einem Zustand, alle 20736 mit zwei und 1048576 mit drei Zuständen in Normalform werden gebaut und ausgeführt - drei Zustände geben höchstens 21 Schritte und höchstens 6 Einsen, von zwei verschiedenen Maschinen. Vier Zustände kosten 268 Millionen Maschinen, also wird dieser Champion als bekannt übernommen und durch einen Lauf geprüft: 107 Schritte, 13 Einsen. Eine Maschine, die die Grenze von 400 Schritten erreicht, hat nicht gehalten, und nichts auf dieser Karte kann sagen, ob sie es je tut.
Gleichungen des Moduls
Gleichungen eine Maschine ist eine Tabelle: Für jedes (Zustand, Symbol) sagt sie, was zu schreiben ist, wohin zu gehen ist (L oder R) und welcher Zustand als Nächstes kommt - oder H, Halt das Band beginnt mit lauter Nullen und ist unbegrenzt; das Fenster der Karte fasst 49 Zellen, genug für jede Maschine, die sie ausführt S(n) - die meisten Schritte, die eine haltende Maschine mit n Zuständen macht; Σ(n) - die meisten Einsen, die eine von ihnen hinterlässt hier durch Aufzählung gefunden, nicht zitiert: n = 1 sind 64 Maschinen, n = 2 sind 20736, n = 3 sind 16^5 = 1048576 in Normalform (erster Zug 1RB) S(1) = 1, Σ(1) = 1; S(2) = 6, Σ(2) = 4; S(3) = 21, Σ(3) = 6 - und für n = 3 sind das zwei VERSCHIEDENE Maschinen das Anheben der Schrittgrenze von 25 auf 200 fügt keine einzige haltende Maschine hinzu: Jede 3-Zustands-Maschine, die hält, hält spätestens bei Schritt 21 n = 4 würde 16^7 = 268435456 Maschinen kosten, daher wird sein Champion als bekannt übernommen und durch Ausführen geprüft: 107 Schritte, 13 Einsen S(n) wächst schneller als jede berechenbare Funktion - deshalb endet die Tabelle oben bei vier und nicht bei zehn
