Zustandsgraphen

Diese Beschreibung kann am einfachsten grafisch veranschaulicht werden. Die entsprechenden Diagramme nennt man Zustandsgraphen. Das folgende Diagramm geht davon aus, dass auf dem Band die Zeichen 1 und 0 sein können.

Dieses Diagramm ist wie folgt zu lesen:

• Wird im Zustand "nach rechts laufen" ein beliebiges Zeichen gelesen, so wird der Kopf um 1 Schritt nach rechts bewegt. Die Maschine verbleibt in diesem Zustand, d.h. sie wiederholt denselben Schritt beim nächsten Mal erneut.
• Trifft die Maschine aber auf ein leeres Feld (kein Zeichen), so wird die Maschine in einen neuen Zustand "am Ende" gebracht, wobei der Kopf um eine Stelle nach links bewegt wird.

Anschaulich beschreibt dieses Turingprogramm eine Anweisung, wie der Kopf von einer beliebigen Stelle aus ans Ende des Bandes (bis vor das nächste leere Feld) bewegt werden kann.