 |
|||
| HSG |
|
Definition und Arbeitsweise einer Turing-Maschine
Definition:
Eine Turing-Maschine besteht aus
- einer nichtleeren, endlichen Menge A von Ein- und Ausgabezeichen , dem Bandalphabet (häufig nur A = {*,I}, dabei steht * für das Leerzeichen)
- der Menge B = {L,R,H} der möglichen Kopfbewegungen
- einer nichtleeren, endlichen Menge Z von Zuständen
- einer Überführungsfunktion fü : ZxA --> Z
- einer Ausgabefunktion fa : ZxA --> A
- einer Bewegungsfunktion fb : ZxA --> B
- einem ausgezeichneten Element s0 aus Z, dem Anfangszustand
Arbeitsweise:
Die Turing-Maschine arbeitet in diskreten Schritten. Zu einem gewissen Zeitpunkt befinde sie sich im Zustand z. Der Schreib-Lese-Kopf liest beim Takt das Zeichen e und geht in den Zustand zneu = fü(z,e) über, wobei er das Zeichen a = fa(z,e) ausgibt. Anschließend wird der Kopf gemäß der Bewegungsfunktion fb(z,e) auf dem Band bewegt. Die Maschine hält, wenn fb die Kopfbewegung H ausgibt. Sie beginnt ihre Arbeit definitionsgemäß im Startzustand s0.
