Turing-Maschine
Über diese App
Das Minimalmodell des Berechenbaren zum Zuschauen: Band, Lese-/Schreibkopf und eine winzige Übergangstabelle. Vorgefertigte Programme (Binär-Inkrement, unäre Addition, Palindrom-Prüfer, Busy Beaver) Schritt für Schritt ablaufen lassen — die aktive Regel leuchtet, der Kopf wandert, und aus 3–5 Regeln entsteht sichtbar ein korrektes Ergebnis.
Mit Erklärmodus: Ein KI-Tutor führt dich durch die App, zeigt in der Szene, worauf es ankommt, und beantwortet deine Fragen.
Was eine Turingmaschine ist
Die Turingmaschine ist Alan Turings Modell von 1936 für alles, was sich berechnen lässt. Sie besteht aus einem unendlichen Band mit Symbolen, einem Kopf, der jeweils eine Zelle liest und beschreibt, und einer endlichen Übergangstabelle. Jede Regel sagt: Im Zustand q mit gelesenem Symbol x schreibe y, bewege den Kopf nach links oder rechts und wechsle in den Zustand q′. Erreicht die Maschine den Haltezustand, ist die Rechnung fertig. Nach der Church-Turing-These kann jedes algorithmisch lösbare Problem so gelöst werden.
Was die App zeigt
Oben läuft das Band mit dem Kopf, über dem der aktuelle Zustand steht, etwa seek, carry oder HÄLT. Daneben steht die Übergangstabelle mit Zeilen für Zustände und Spalten für gelesene Symbole; die gerade greifende Regel leuchtet. Ein Zähler zeigt die Schritte. Vier vorgefertigte Programme stehen zur Wahl: Binär-Inkrement, unäre Addition, Palindrom-Prüfer und Busy Beaver. Ein Info-Panel erklärt das jeweilige Programm.
Selbst ausprobieren
Wähle ein Programm, stelle ein langsames Tempo ein und gehe Regel für Regel mit dem Schritt-Knopf vor, oder lass die Maschine laufen. Beim Binär-Inkrement sieht man, wie der Kopf ans Ende läuft und den Übertrag nach links trägt. Der Busy Beaver zeigt, wie viele Einsen eine Maschine mit sehr wenigen Zuständen schreiben kann, bevor sie hält.
Häufige Fragen
- Woraus besteht eine Turingmaschine?
- Aus einem unendlich langen Band, das in Zellen mit Symbolen eingeteilt ist, einem Lese-/Schreibkopf, einer endlichen Menge von Zuständen und einer Übergangsfunktion. Diese legt für jedes Paar aus Zustand und gelesenem Symbol fest, was geschrieben wird, wohin der Kopf geht und welcher Zustand folgt.
- Was ist ein Busy Beaver?
- Ein Busy Beaver ist eine Turingmaschine mit n Zuständen, die auf leerem Band startet, irgendwann hält und dabei so viele Einsen schreibt oder so viele Schritte macht wie keine andere Maschine dieser Größe. Die Busy-Beaver-Funktion wächst schneller als jede berechenbare Funktion und ist selbst nicht berechenbar.
- Warum ist die Turingmaschine so wichtig?
- Sie präzisiert den Begriff „berechenbar“. Alles, was ein heutiger Computer kann, kann im Prinzip auch eine Turingmaschine, nur langsamer. An ihr hat Turing gezeigt, dass manche Fragen, etwa ob ein beliebiges Programm anhält (Halteproblem), grundsätzlich nicht algorithmisch entscheidbar sind.
- Welche Programme laufen in der App?
- Binär-Inkrement (eine Binärzahl um 1 erhöhen), unäre Addition, ein Palindrom-Prüfer und ein Busy Beaver. Du kannst jedes Schritt für Schritt oder automatisch in wählbarem Tempo ablaufen lassen und siehst dabei, welche Regel greift.
Fach: Informatik
Mehr aus Informatik
- Ackermann-Funktion
- Aufzug-Simulator
- Binär-Werkstatt
- Binäre vs. lineare Suche
- Collatz-Problem (3n+1)
- CPU-Innenleben
- Das Innere austauschen
- Ein Frame in 16 Millisekunden — wie eine Game-Engine ein Bild rechnet (3D)
Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps