Bei der Turingmaschine handelt es sich um ein von Alan Turing 1936 enwickeltes Rechnermodell. Sie besitzt einige Eigenschaften des Kellerautomaten und modelliert eine simple Form eines Computers.

Die Maschine besteht dabei aus 3 Bestandteilen:

1. Ein Ein-/Ausgabeband, welches als Speicher fungiert. Dabei steht sowohl die Ein-, als auch die Ausgabe auf dem Band.
2. Ein Lese- und Schreibkopf, welcher die Zeichen auf dem Band lesen kann. Außerdem kann er auf das Band Zeichen schreiben.
3. Die Steuereinheit bzw. das Programm bestimmt in Abhängigkeit eines aktuellen Zustandes und des eingelesenen Zeichens, welches Zeichen auf das Band geschrieben werden soll.

Übergangsgraph

Die Übergänge bei der Turingmaschine sind ähnlich wie bei einem Kellerautomaten aufgebaut. Dabei wird zuerst das Zeichen auf dem Band an der Stellle eingelesen, an welcher sich der Lesekopf befindet. Durch das Lesen des Zeichens wird dieses automatisch gelöscht. Dann wird festgelegt, welches neue Zeichen an die Stelle geschrieben werden soll. Als letzter Schritt wird dann festgelegt, in welche Richtung sich der Lesekopf bewegen soll (L,R,N).

Eingelesenes Zeichen; neues Zeichen, Bewegung des Lesekopfes

Die obige als Übergangsgraph dargestellt Turingmaschine überprüft, ob eine Eingabe zu folgender Sprache gehört:

Um eine Eingabe zu überprüfen, wird für jedes a ein b gelöscht bzw. durch ein leeres Zeichen ersetzt. Wenn am Ende nur noch leere Zeichen vorhanden sind, ist die Eingabe valide.

Formale Definition

Eine Turingmaschine kann durch ein sieben-Tupel definiert werden:

$\Sigma$: endliche Menge aus Eingabezeichen (Eingabealphabet).

$\Gamma$: endliche Menge aus Bandzeichen (Bandalphabet).

$S$: endliche Menge an Zuständen.

$R$: Zustandsüberführungsfunktion

$s_0$: Startzustand

$b_0$: Bandleerzeichen

$F$: endliche Menge an Endzuständen