Zustand
Schritte
Symbole auf dem Band
Status

Im Zustand Liest Schreibt Bewegt sich Nächster Zustand

Mehr über Turingmaschinen

Turingmaschinen-Simulator

Eine Turingmaschine ist der einfachste denkbare Computer: ein Kopf, der ein Symbol eines endlosen Bandes liest, ein Symbol schreibt, eine Zelle nach links oder rechts rückt und seinen Zustand wechselt, nach einer kurzen Tabelle von Regeln. Alan Turing erfand sie 1936, und alles, was Ihr Computer tut, ließe sich im Prinzip auf diese Weise erledigen. Schreiben Sie eigene Regeln oder laden Sie ein Beispiel, drücken Sie auf Ausführen und sehen Sie zu, wie sich das Band Schritt für Schritt verändert, mit einem Diagramm seiner ganzen Geschichte darunter. Wählen Sie ein Programm oder schreiben Sie ein eigenes, geben Sie die Eingabe ein und drücken Sie auf Ausführen, oder auf Schritt, um Regel für Regel zu folgen; Zurück macht einen Schritt rückgängig. Jede Zeile des Programms ist eine Regel: Zustand, gelesenes Symbol, zu schreibendes Symbol, Bewegung (L, R oder N für keine Bewegung) und nächster Zustand, zum Beispiel A 0 -> 1 R B. Verwenden Sie _ für eine leere Zelle. Die Maschine beginnt im Zustand der ersten Regel auf dem ersten Symbol der Eingabe und hält in H, accept oder reject an oder wenn keine Regel passt. Das Diagramm zeigt das Band nach jedem Schritt, von oben nach unten.

Wie es funktioniert

  1. Wählen Sie ein Beispielprogramm oder schreiben Sie Regeln wie A 0 -> 1 R B, eine pro Zeile, und tippen Sie die Eingabe ein.
  2. Drücken Sie auf Ausführen, um den Kopf wandern zu sehen, oder auf Schritt, um Regel für Regel zu folgen; Zurück macht einen Schritt rückgängig.
  3. Lesen Sie in den Kacheln den Zustand, die Schritte und die Symbole auf dem Band ab und im Diagramm die Geschichte des Bandes.

So funktioniert die Maschine

In jedem Moment befindet sich die Maschine in einem von wenigen Zuständen, und ihr Kopf steht auf einer Zelle des Bandes. Die Regel für diesen Zustand und das Symbol unter dem Kopf legt drei Dinge fest: welches Symbol in die Zelle geschrieben wird, ob sich der Kopf nach links, nach rechts oder gar nicht bewegt und in welchen Zustand die Maschine als Nächstes wechselt. Das ist die ganze Maschine. Sie hält an, wenn sie einen Haltezustand wie H, accept oder reject erreicht oder wenn keine Regel passt. Ein Programm, das 1 zu einer Binärzahl addiert, braucht nur neun solcher Regeln.

Fleißige Biber

Welche Maschine mit n Zuständen schreibt, auf einem leeren Band gestartet, die meisten Einsen, bevor sie anhält? Diese Frage stellte Tibor Radó 1962. Die Champions heißen fleißige Biber, und sie wachsen schneller als jede Funktion, die ein Computer berechnen kann. Zwei Zustände ergeben 4 Einsen in 6 Schritten, drei Zustände 6 Einsen, vier Zustände 13 Einsen in 107 Schritten. Der Champion mit fünf Zuständen, 1989 gefunden, schreibt 4.098 Einsen in 47.176.870 Schritten, und 2024 bewies eine Online-Zusammenarbeit mit computergeprüfter Mathematik, dass keine andere anhaltende Maschine mit fünf Zuständen länger läuft.

Häufig gestellte Fragen

Wie schreibe ich eine Regel?

Eine Regel pro Zeile: der aktuelle Zustand, das gelesene Symbol, das zu schreibende Symbol, die Bewegung (L, R oder N) und der nächste Zustand, zum Beispiel A 0 -> 1 R B. Pfeil und Kommas sind optional. Verwenden Sie _ für eine leere Zelle und # für einen Kommentar. Die Maschine beginnt im Zustand der ersten Regel; ein nächster Zustand namens H oder halt hält sie an, und accept und reject halten sie mit einem Urteil an.

Kann eine Turingmaschine wirklich alles berechnen?

Alles, was irgendein Computer berechnen kann, sofern genug Band und Zeit vorhanden sind: Das ist die Church-Turing-These. Eine Turingmaschine hat keine Speichergrenze und ist in diesem Sinne mächtiger als jeder reale Computer, wenn auch weit langsamer. Was sie nicht kann, ist jede Frage beantworten: Turing bewies, dass keine Maschine für jedes Programm und jede Eingabe entscheiden kann, ob es anhält.

Warum hält der Zähler nie an?

Seine Regeln führen nie in einen Haltezustand. Er addiert immer wieder 1 zu einer Binärzahl am rechten Ende des Bandes und läuft zurück, sodass die Zahl endlos wächst. Turings Halteproblem besagt, dass keine allgemeine Methode für jede Maschine sagen kann, ob sie anhält; bei diesem einfachen Zähler sieht man es, doch bei manchen Maschinen mit nur sechs Zuständen weiß es bis heute niemand.

Wie kann der fleißige Biber mit fünf Zuständen hier 47 Millionen Schritte laufen?

Das Band wird als kompaktes Array gespeichert, das in beide Richtungen wächst, und auf der Stufe „Sehr schnell“ führt die App zwischen zwei Bildschirmaktualisierungen Hunderttausende von Schritten aus, sodass der ganze Lauf in einem modernen Browser wenige Sekunden dauert. Das Diagramm zeichnet nur die ersten 400 Schritte auf, denn ein Bild mit 47 Millionen Zeilen würde auf keinen Bildschirm passen.

Wird etwas an einen Server gesendet?

Nein. Das Programm läuft in Ihrem Browser, und Ihr Programm und Ihre Eingabe bleiben im lokalen Speicher dieses Browsers.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Zum Editor