Eine Turing-Maschine kann man sich als ein Gerät vorstellen, das
aus einer Kontrolleinheit , einem
Schreib/Lesekopf und einem einseitig unbegrenzten
Band besteht.
Wie ein endlicher Automat kann
die Kontrolleinheit endlich viele interne Zustände annehmen.
Das Band ist in einzelne Felder unterteilt, die
genau ein Zeichen aufnehmen können.
Der Schreib/Lesekopf kann zu jedem Zeitpunkt genau ein Feld lesen oder
verändern. Außerdem kann der Kopf (bzw. das Band) schrittweise nach
links oder rechts bewegt werden.
Das Eingabealphabet enthält Symbole, die ''irgendwie von
außen'' auf das Band geschrieben wurden.
Das Bandalphabet besteht aus allen Zeichen, die die Turing-Maschine
verarbeiten kann. Das sind mindestens die Zeichen des Eingabealphabets
und ein Spezialsymbol (*), das anzeigt, daß ein Feld
leer/undefiniert ist.
Definition: (Turing-Maschine [9])
Eine Turing-Maschine T ist durch ein Sechstupel 
definiert, wobei
das Eingabealphabet 
,
das Bandalphabet 
,
die Zustandsmenge ,
eine partielle Funktion,
die Überführungsfunktion ,
der Anfangszustand und
die Menge der Endzustände ist.
Die Funktionsweise einer Turing-Maschine ist durch die
Überführungsfunktion festgelegt:
bedeutet, daß die Turing-Maschine, wenn im Zustand s das Zeichen b gelesen
wird, in den Zustand s' wechselt und b durch b' ersetzt. Danach
bewegt sich der Kopf um einen Schritt nach links (X = L), nach
rechts (X = R) oder bleibt unverändert (X = N).
Üblicherweise stellt man 
als Tabelle (Turing-Tafel ) dar:
 | b | ... |  | |
 | ||||
 | ||||
| ... | ||||
| s | (s', b', X) | |||
| ... | ||||
 |
Die Turing-Maschine hält, falls für das aktuelle Paar (s, b) nicht
definiert ist.
Turing-Maschine, die das letzte Zeichen des Eingabewortes auf dem Band sucht:
| 0 | 1 | * | ||
| |  |  |  | |
|
| -- | -- | -- |
Turing-Maschine, die das Eingabewort auf dem Band löscht:
| 0 | 1 | * | ||
| |  | |  | |
|
| -- | -- | -- |
Turing-Maschine, die eine Zahl in unärer Darstellung um 1 vergrößert:
| 1 | * | |
| | |  |
|
| -- | -- |
Hier wird vorausgesetzt, daß die Turing-Maschine auf der ersten 1 steht, wenn sie gestartet wird.
Die folgende Turing-Maschine wird links von der
Bandinschrift gestartet, sucht dann den Anfang der Eingabe, geht zum
Ende und verlängert die Inschrift um 1.
| 1 | * | |
| | | |
|
| |  |
 | -- | -- |
Definition:(Bandinschrift)
Die Bandinschrift einer Turing-Maschine ist ein Wort über dem
Bandalphabet, das mit dem Zeichen im ersten Feld des Bandes beginnt
und endet
Definition:(Konfiguration, Übergangsrelation [9])
Es sei eine Turing-Maschine.
Eine Konfiguration von T ist ein Tupel 
. Dabei ist vbw als die aktuelle
Bandinschrift und s als der aktuelle Zustand zu
interpretieren. Ferner befindet sich der Schreib/Lesekopf auf dem Feld
mit dem Zeichen b.
Die Übergangsrelation 
beschreibt alle möglichen durch
hervorrufbaren Übergänge einer Konfiguration zu einer
Folgekonfiguration., d.h. für 
und 
wird definiert:
(1) falls X = N:
(v, b, w, s) (v, b', w, s')
(2) falls X = R:
(v, b, w, s) 
(3) Falls X = L und 
(v, b, w, s) 
bezeichne wieder die reflexiv-transitive Hülle von .
Turing-Maschine, die eine natürliche Zahl n, die durch n Striche auf dem
Eingabeband dargestellt wird, verdoppelt:
| 1 | * | |
| |  | |
|
| |  |
|
| |  |
 | |  |
 |  |  |
 | |  |
 | |  |
 |  |  |
 | -- | -- |
Was tut die folgende ?
| 1 | * | |
| | | |
|
| |  |
|
|  |  |
|
|  |  |
|
|  |  |
|
| | |
|
| -- | -- |
Turing-Maschine, die eine Binärzahl, die mindestens eine Null enthält, um 1
erhöht:
| 1 | 0 | * | |
| | | | |
|
|  | | -- |
|
| -- | -- |
Prof. Dr. Reinhard Völler