Zustandstafel einer Turingmaschine

Die Zustandstafel einer Turingmaschine

Seien s0 und s1 Zustände eine Turingmaschine, und se der zulässige Endzustand einer Turingmaschine. Auf dem Band kommen die Zeichen a,b, Q, T und * (* steht für ”nichts”) vor. Eine Zustandstafel veranschaulicht die Überführungsfunktion der Turingmaschine:

d a b *
s0 (s0,a,R) (s0,b,R) (s1,Q,L)
s1 (s1,a,L) (s1,b,L) (se,T,N)
se - - -

Anhand der Zustandstafel sehen wir was die Turingmaschine in Wahrheit macht. Die oben repräsentierte Turingmaschine liest erstmal das ganze Band durch, bis man ganz am rechten Ende der Eingabe ist. Hier wird dann auf die erste leere Stelle ein Q eingeschrieben. Danach bewegt sich die Turingmaschine wieder ans linke Ende der Eingabe, wo ein T in die erste leere Stelle eingeschrieben wird. Danach bewegt sich die Turingmaschine nicht mehr und begibt sich in den Endzustand.