Alan Turing führte diese nach ihm benannten Maschien 1936 zum theoretischen Studium der Berechenbarkeit ein. Eine Turing-Maschine arbeitet auf einem einseitig unendlichen Band, das in unendlich viele Zellen an (n = 0, 1, 2, ...) aufgeteilt ist, die jeweils ein Wort aus dem verwendeten Alphabet E (z.B. E={1, 0} oder E={0, 1, X, Y} usw.) enthalten können. Die Maschine beginnt am Anfang des Bandes (Tape) mit ihrer Arbeit (a0). Die Maschine selber ist in einen festen ("Hardware") und einen variablen Teil ("Software" bzw. "Programm") aufgeteilt. Die Turing-Maschinen beschreiben also eigentlich eine ganze Klasse von Maschinen (unendlich viele!), weil das Programm, das nach bestimmten Regeln aufgebaut sein muss, unendlich lang und komplex sein kann. Den Aufbau einer Turing-Maschine zeigt die folgende Abbildung:
Die Maschine befindet sich zu jedem Zeitpunkt in einem definierten inneren Zustand Z. Zu Anfang ist dies der Startzustand Z*, der im Programm festgelegt wird. Sobald die Maschine mit ihrer Arbeit fertig geworden ist, befindet sie sich im Endzustand Z#, der ebenfalls im Programm definiert wird. Sie hört dann auf mit der Arbeit.
Ein Turing Maschine hat einen Schreib-/Lesekopf als einzige Hardware, der immer genau auf eine Zelle des Bandes am zeigt. Er stellt am Anfang eines Zykluses den Wert der Zelle unter ihm zur Verfügung und schreibt nach der Auswertung das Ergebnis an die selbe Stelle am des Bandes. Danach wandert er je nach Anweisung im Programm um eine Position nach rechts oder links. Zum Schluss geht die Maschine noch in einen neuen internen Zustand über.
Im Programm wird je nach innerem Zustand Z und gelesenem Wert am entschieden, was geschrieben werden soll und in welche Richtung sich der Schreib-/Lesekopf bewegen soll. Dabei muss immer etwas geschrieben werden und der Kopf muss sich immer bewegen (er kann also nicht stehen bleiben). Somit kann man ein Programm für eine Turing-Maschine als Tabelle schreiben, bei der jede Zeile genau einer Kombination von internem Zustand und gelesenem Wert entspricht. Der Ablauf eines solchen Zykluses wird in der folgenden Graphik leicht verständlich:
Hier ein beispiel für ein kleines Turing-Maschinen-Programm:
| Zustand | Eingabe | Operation (Ausgabe, Verschiebung) | Folgezustand | Bemerkung |
| A | 1 | 0,rechts | A | Anfangszustand Z* |
| 0 | 0,rechts | B | ||
| B | Endzustand Z# |
Das Programm lässt sich auch als Graph darstellen und wird so leichter verständlich:
Das Programm besagt folgendes:
|
|
|
|
|
|
|
|
|
|
|
Auf diesem Tape würde das Programm alle "1" durch "0" ersetzen und bei der ersten "0" in den Endzustand übergehen und sich beenden.
Im unteren Teil des Fenster gibt es vier Buttons für die Bedienung der Programms und ein Eingabefeld, in das man ein Zeit-Intervall (in Millisekunden) eingeben kann, das zwischen zwei Zyklen der Maschine liegt.
Der aktuelle Zustand von Band und maschine wird ganz unten angezeigt.
Die Buttons haben folgende Bedeutung:
Ein Programm sieht folgendermaßen aus:
;Beispielprogramm: Löschen einer Kette aus dem Zeichen "1" *1 1 0,rechts 1 ;Anfangszustand 1 0 0,rechts 2 #2 ;Endzustand |