Man kann Turingmaschinen
als Erweiterung von Linear beschränkten Automaten verstehen.
Das Arbeitsband kann sowohl gelesen als auch beschrieben werden; es ist in beide Richtungen unendlich.
Zur Speicherung von Zwischenergebnissen stehen somit theoretisch unendlich viele Zellen zur Verfügung.
Neben dem Arbeitsband besitzen sie einen Lese-/Schreibkopf und eine Kontrolleinheit.
Der Kopf kann sich in beiden Richtungen über das Arbeitsband bewegen.
Durch ein besonderes Symbol, 'B' (blank) wird eine leere Zelle markiert.
In der Anfangskonfiguration enthalten alle nicht durch das Eingabewort belegten Zellen dieses Symbol und
der Kopf liest das erste Zeichen der Eingabe.
Die Folgekonfiguration wird durch das aktuelle Symbol und den aktuellen Zustand bestimmt.
Ein Übergang von einer Konfiguration in die nächste lässt sich durch folgende Aktionen charakterisieren:
- Wechsel in einen vom aktuellen Zustand verschiedenen Zustand oder keine Änderung
- Schreiben eines gegebenen Symbols in die aktuelle Zelle oder keine Änderung
- Bewegen des Lese-/Schreibkopfes nach Links oder Rechts
| 
Formale Darstellung von TM
