Deterministische Turing-Maschine

Eine DTM ist ein Septupel (ein 7-Tupel) $M=(Z,\Sigma ,\Gamma ,\delta ,z_0,\square ,E)$ mit:

1. $Z$: Eine endliche Menge von Zuständen.
2. $\mathrm{\Sigma }$: Das Eingabealphabet (Zeichen, die am Anfang auf dem Band stehen).
3. $\mathrm{\Gamma }$: Das Arbeits- oder Bandalphabet (alle Zeichen, die auf das Band geschrieben werden dürfen, $\mathrm{\Sigma }\subseteq \mathrm{\Gamma }$).
4. $\delta$: Die partielle Überführungsfunktion (das "Programm").
5. $z_0$: Der Startzustand.
6. $◻$: Das Blanksymbol (ein Zeichen in $\mathrm{\Gamma }$, aber nicht in $\mathrm{\Sigma }$, das "leere" Zellen füllt).
7. $E$: Die Menge der Endzustände.