Turingmaschine
Einfache Sprache
DEA erweitern durch unendliche viele Zustände -> Speicherrestriktion aufheben aber so minimal hinzugeben damit die Maschine immer noch mit möglichst wenigen Annahmen und im Umkehrschluss möglichst generell ist. Die simpelste Form ist mit einem “endlosen” Band.
Es gibt 4 Möglichkeiten eine TM zu beschreiben:
- Formale Beschreibung; korrekte mathematische Definition
- Graphische Beschreibung; durch ein Zustandsdiagramm
- High-level Beschreibung; Konkrete Implementation mit Details
- Informelle Beschreibung; allgemeine Beschreibung ohne Details
Es wird zwischen DTM und NDTM unentschieden. Arten:
Syntax
Eine Turingmaschine (TM) ist eine Struktur $(Q,A,\Gamma,\delta,q_0,\textvisiblespace,q_{acc},q_{rej})$ mit:
- $Q$ - endliche Menge (Zustände)
- $A$ - endliche Menge (Eingabealphabet) mit $\textvisiblespace\notin A$
- $\Gamma$ - endliche Menge (Bandalphabet) mit $(A\cup\{\textvisiblespace\})\subseteq\Gamma$
- $q_0\in Q$ (Anfangszustand)
- $q_{acc}\in Q$ (akzeptierender Zustand)
- $q_{rej}\in Q$ (verwerfender Zustand) mit $q_{acc}\neq q_{rej}$
- $\delta:(Q\setminus\{q_{acc},q_{rej}\})\times\Gamma\rightarrow\mathcal{P}(Q\times\Gamma\times\{L,R,N\})$. Bemerke das dies die Definition eine NDTM ist.
Anmerkungen
- Wir schreiben $q,a\longrightarrow p,b,r$ falls $(p,b,r)\in\delta(q,a)$ mit $q,p\in Q,\;a,b\in\Gamma,\;r\in\{L,R,N\}$
- Die deterministische Variante bekannt als DTM definiert $\delta$ wie folgt: $\delta(Q\setminus\{q_{acc},q_{rej}\})\times\Gamma\rightarrow Q\times\Gamma\times\{L,R,N\}$
- $\{L,R,N\}$ sind die Richtungen in die der Schreib-Lese-Kopf als nächstes sich bewegt: Links, Rechts und Neutral (gar nicht).
Semantik
Zentrale Begriffe
Erkennen
Eine TM erkennt eine Sprache, deren Wörter sie akzeptiert.
Entscheiden
Eine TM entscheidet eine Sprache, wenn für jedes Wort eine endliche Berechnung existiert.
“Turing” Sprache?
Sei $\mathcal{M}$ eine TM. Dann sei die Sprache welche die TM abbildet wie folgt definiert $L(M)=\{w\in A^*|es existiert eine akzeptierende Berechnung\}$.