Turingmaschine 81

Definition 81

Eine Touringmaschine (Kurz: TM) ist gegeben durch ein 7-Tupel

$$M=\left(Z,\Sigma,\Gamma,\delta,z_{0},\square,E\right)$$

• $Z$ die endliche Zustandsmenge
• $\Sigma$ das Eingabealphabet
• $\Gamma\supset\Sigma$ das Arbeitsalphabet
• $\delta:Z\times\Gamma\rightarrow Z\times\Gamma\times\left\{ L,N,R\right\}$ im deterministischen Fall
  (bzw. $\delta:Z\times\Gamma\rightarrow\mathcal{P}\left(Z\times\Gamma\times\left\{ L,N,R\right\} \right)$ im nichtdeterministischen Fall)
  die Überführungsfunktion
• $z_{0}\in Z$ der Startzustand
• $\square\in\left(\Gamma\backslash\Sigma\right)$ das Blank (Leerzeichen)
• $E\subseteq Z$ die Menge der Endzustände

Die Überführungsfunktion bedeutet informal:
${\scriptstyle \delta\left(\mathrm{alter\: Zustand},\mathrm{Symbol\, vor\, Lese... ...{neues\, Symbol\, auf\, Band},\mathrm{Kopfbewegung\, LinksRechtNeutral}\right)}$

Eine Konfiguration der TM $M$ ist ein Wort $k\in\Gamma^{*}Z\Gamma^{+}$. $k$ deckt den von $\square$ verschiedenen Teil des Bandes ab. Dabei sind die einzelnen Teile des Wortes: Band Links vom Lesekopf; Akt. Zustand; Band unter und Rechts vom Lesekopf.

Die Startkonfiguration für Eingabe $x\in\Sigma^{*}$ ist $z_{0}x$.

Die Berechnungsrelation $\vdash$ ersetzt den Zustand durch den neuen Zustand, ersetzt das Symbol auf dem Band durch das neue Symbol, und führt die Kopfbewegung aus, indem bei L (R) ein Zeichen von Links nach Rechts neben dem Zustand (bzw. andersherum) bewegt wird. Falls sich der Kopf am Bandrand befindet, können an den Rändern zusätzliche $\square$ eingefügt werden.

Die von einem TM $M=\left(Z,\Sigma,\Gamma,\delta,z_{0},\square,E\right)$ akzeptierte Sprache ist definiert als

$$T\left(M\right)=\left\{ x\in\Sigma^{*}\vert z_{0}x\vdash^{*}\alpha z\beta\left(\alpha,\beta\in\Gamma^{*},z\in E\right)\right\}$$

• Die durch allgemeine TMen akzeptierten Sprachen sind genau die Typ 0 Sprachen

Linear Beschränkte Turingmaschinen 84

Eine nichtdeterministische TM $M$ heißt linear beschränkt, wenn für alle $a_{1}a_{2}\ldots a_{n-1}a_{n}\in\Sigma^{+}$ und alle Konfigurationen $\alpha z\beta$ mit $z_{0}a_{1}a_{2}\ldots a_{n-1}\hat{a_{n}}\vdash^{*}\alpha z\beta$ folgendes gilt: $\left\vert\alpha\beta\right\vert=n$.

Hierbei ist $\Sigma'=\Sigma\cup\left\{ \hat{a}\vert a\in\Sigma\right\}$ (Alphabet um modifizierte Symbole ergänzt)

$T\left(M\right)=\left\{ a_{1}a_{2}\ldots a_{n-1}a_{n}\in\Sigma^{*}\vert z_{0}a... ...n}\vdash^{*}\alpha z\beta\left(\alpha,\beta\in\Gamma^{*},z\in E\right)\right\}$

Informal bedeutet dies, das der TM nur ein Band der Länge $n$ zurverfügung steht, und alle Berechnungen auf diesem Durchgeführt werden. Dazu muss Das letzte Zeichen auf dem Band markiert werden, damit die Maschine das Ende erkennt. Das erste Zeichen ist wird als erstes beim Start gekennzeichnet, da die Maschine hier beginnt.

• Die von linear beschränkten, nichtdeterministischen TMen (LBAs) akzeptierten Sprachen sind genau die kontextsensitiven Sprachen.