Sieben Komponenten sind nötig, um eine TM zu beschreiben.
Bestandteile sind das Bandalphabet, das aus den Symbolen besteht, die eine Bandzelle enthalten kann.
Dazu gehört auch das sogenannte 'Blank' B, das eine leere Zelle bezeichnet.
Das Eingabealphabet besteht aus einer Teilmenge des Bandalphabets.
Das B-Symbol darf jedoch nicht Bestandteil des Eingabealphabets sein.
Die Gründe dafür sind offensichtlich: Die TM hätte keine Möglichkeit zwischen einer leeren Zelle und einem
durch 'B' bezeichneten Wortteil zu unterscheiden.
Zustandsmenge, Startzustand und Endzustände sind wie bei den anderen Automatentypen aufgebaut.
Die Übergangsfunktion muss nicht vollständig definiert sein.
Aus dem gegenwärtigem Zustand und dem aktuellen Bandsymbol berechnet sich der Folgezustand, das neue Bandsymbol
und die Aktion des Lese-/Schreibkopfes. Die Aktion des Lese-/Schreibkopfes wird durch L und R bezeichnet - stellvertretend für
Bewegung nach links bzw. Bewegung nach rechts. Für den Fall S (stopp) hält die Turingmaschine an.
Die Sprache einer Turingmaschine besteht aus denjenigen Wörtern über dem Eingabealphabet,
für die die Turingmaschine in einem Endzustand anhält.
Die Turingmaschine beendet die Berechnung in drei Fällen:
- Falls sie einen Endzustand erreicht. In diesem Fall gehört das Eingangswort zur Sprache der TM und die Ausgabe besteht aus dem Inhalt des Arbeitsbandes.
- Falls ein Übergang undefiniert ist.
- Falls die Übergangsfunktion die Aktion 'S' vorsieht.
| 
1
2
3
4
5
Beispiel
