Turingmaschinen-Simulator

Eine Turingmaschine ist ein mathematisches Modell der Berechenbarkeit aus einem unendlichen Band, einem Lesekopf und einer Übergangstabelle. Sie definiert die Grenzen des Berechenbaren: Jeder Algorithmus kann von einer Turingmaschine simuliert werden. Das Halteproblem beweist die Unentscheidbarkeit, dass kein Algorithmus vorhersagen kann, ob ein Programm jemals stoppt.

Eine Turingmaschine besteht aus fast nichts: einem Band, einem Kopf, der eine Zelle liest, und einer kurzen Regeltabelle. In jedem Schritt prüft sie nur ihren aktuellen Zustand und das Symbol unter dem Kopf, schreibt dann ein Symbol, bewegt sich eine Zelle nach links oder rechts und wechselt den Zustand. Starte die Voreinstellung „Binäres Inkrement“ und beobachte, wie sie nach rechts bis zum Ende gleitet und die +1 nach links zurückträgt — genau wie beim schriftlichen Addieren.

Stelle die kleinste Frage — wie lange kann eine winzige Maschine laufen, bevor sie hält? — und die Berechnung explodiert. Eine Maschine mit 5 Zuständen und 2 Symbolen läuft genau 47,176,870 Schritte, bevor sie stoppt; dieser Wert wurde erst 2024 bewiesen. Bei 6 Zuständen übertrifft der bekannte Rekord bereits 2↑↑↑5, einen Potenzturm, der jedes Atom im Kosmos in den Schatten stellt. Deshalb begrenzen Simulatoren wie dieser jeden Lauf: eine Handvoll Zustände kann die Ewigkeit überdauern.