Test mit Aufgaben

Eine Turingmaschine ist ein Tupel

$T=(Z,E,A,d,q,F)$

Hierbei sind:

• $Z$ eine endliche, nichtleere Menge von Zuständen

• $E$ das Eingabealphabet

• $A$ das Arbeitsalphabet, wobei $E\subseteq A$

• $d$ die Übergangsrelation mit $d\subseteq Z\times A\times A^{\prime }\times Z$, wobei $A^{\prime }=A\cup \{L,R\}$

• $q\in Z$ der Startzustand

• $F\subseteq Z$ die Menge der Endzustände

Das Arbeitsalphabet enthält als spezielle Zeichen das Bandbegrenzungszeichen $\$$ und das Leerzeichen _ ; diese Zeichen kommen nicht im Eingabealphabet vor.

Die Zeichen $L$ und $R$ sind die Cursor-Aktionen "gehe ein Feld nach links" und "gehe ein Feld nach rechts"; diese Zeichen kommen nicht im Arbeitsalphabet vor.

lkjl