Theoretische Informatik - Turingmaschinen (kurz: DTM oder NTM)

Nächste Seite: Registermaschine Turingmaschine Aufwärts: Berechenbarkeit Vorherige Seite: Registermaschinen (kurz: RM) Inhalt

Unterabschnitte

Turingmaschinen (kurz: DTM oder NTM)

Einbandige ,,normale'' Turingmaschinen (deterministisch)

Eine DTM (deterministische Turingmaschine⁴) ist ein 7er-Tupel
$\tau=(Q,\Sigma,\Gamma,\delta,q_{0},\Box,F)$ :

Q	Zustandsmenge
$\Sigma$	Eingabealphabet
$\Gamma$	Bandalphabet
$\delta$	partielle Übergangsfunktion, der Form $\delta(q,a)=(q,a,move)$
$q_{0}$	Startzustand ( $q_{0}\in Q$ )
$\Box$	Blanksymbol ( $\Box\notin\Sigma,\Box\in\Gamma$ )
	Endzustandsmenge ( $F\subseteq Q$ )

Es gibt ein Band und einen aktuellen Zustand auf den der Zeiger der Turingmaschine zeigt. Ein Raum auf dem Band heißt Bandzelle oder Bandquadrat.
Eine partielle Übergangsfunktion hat die Form

$\begin{displaymath}\delta (q_{1},a)=(q_{2},b,N)\end{displaymath}$

Eine Turingmaschine kann

akzeptieren	Wenn $q_{aktuell}\in F$ . Dabei ist es unerheblich, ob die partielle Funktion $\delta$ noch weiterrechnen könnte. Sobald ein Endzustand erreicht ist, ist Ende.
verwerfen	Wenn $\delta(q_{aktuell},Zeichen_{aktuell})=\bot$ . Verwerfen tut sie, wenn der aktuelle Zustand kein Endzustand ist und ,,es nicht mehr weiter geht''.
endlos laufen	Wenn sie niemals abbricht.
*Fangzustand*	Die Turingmaschine kann in einen Fangzustand geraten. In einem Fangzustand arbeitet die Turingmaschine dauernd eine Übergangsfunktion folgender Form ab: $\begin{displaymath}\delta(q_{aktuell},Zeichen_{aktuell})=(q_{aktuell},Zeichen_{aktuell},N)\end{displaymath}$ Fangzustände können auch formal durch verwerfende Zustände ersetzt werden.

Mehrbandige Turingmaschinen

Bei mehrbandigen Turingmaschinen hat die Übergangsfunktion die Form

$\begin{displaymath}\delta(q,(a,b))=(p,<c,L>,<d,R>)\end{displaymath}$

Eine Konfiguration wird wie folgt dargestellt:

$\begin{displaymath}\left(\begin {array}{c}\alpha_{1}\\ \vdots \\ \alpha_{k}\\ \e... ...n {array}{c}\beta_{1}\\ \vdots\\ \beta_{k}\\ \end{array}\right)\end{displaymath}$

Nichtdeterministische Turingmaschinen

Übergangsfunktion:

$\begin{displaymath}\delta(q,a)=\{(q_{1},b_{1},X_{1}),\ldots,(q_{k},b_{k},X_{k})\}\end{displaymath}$

Die Konfiguration ist ein Baum.

Kosten von Turingmaschinen

Zeitkomplexität:
$t_{\tau}(w)$ = Anzahl der Konfigurationswechsel, die $\tau$ bei der Eingabe

durchführt.
Platzkomplexität:
$s_{\tau}(w)$ = Anzahl der Bandzellen, die $\tau$ bei der Eingabe

besucht.

Ferner gilt:

$\begin{displaymath}s_{\tau}(w)\leq t_{\tau}(w)+1\end{displaymath}$

,da die Turingmaschine auch sofort abbrechen kann. In diesem Fall würden zwar eine Bandzelle besucht aber keine Zeit verbraucht werden. Es würde stehen $1\leq 0+1$ . Man sieht, daß die

von Nöten ist.

Simulation von mehrbandigen Turingmaschinen durch einbandige Turingmaschinen

Jede Mehrbandturingmaschine kann durch eine Einbandturingmaschine simuliert werden und umgekehrt.

,, $\Leftarrow$ '': Ist trivial. Jede Einbandturingmaschine kann man auf einer Mehrbandturingmaschine simulieren, indem man nur ein Band der Mehrbandturingmaschine benutzt.

,, $\Rightarrow$ '': Man kann aus einer Mehrband-DTM folgendermaßen eine Einband-DTM machen:

Man erweitert die DTM auf auf Bänder. Jeweils auf dem -ten Band setht ein Zeichen, welches die Zeigerposition zeigt, auf dem -ten Band ist dsa normale Band zu finden.
Nun erweitert man das Bandalphabet so, daß zu jeder Kombination an Zeichen auf den Bandzellen ein Zeichen in diesem Alphabet vorhanden ist:

$\begin{displaymath}\Gamma' = \Gamma \cup (\Gamma\cup\{\ast\})^{2k}\end{displaymath}$

Weiterhin wird auch die Zustandsmenge in verändert. In den Zuständen ist für jeden Zustand eine Zustandsmenge vorhanden. In dieser werden die Zeichen, die unter den Zeigern der Mehrbandturingmaschine stehen gespeichert und dann hinterher eine Bewegung auf allen virtuellen Bändern ausgeführt⁵.
Wir verfahren nun bei der Simulation wie folgt:
1. Wir suchen alle Zeiger auf dem Band und speichern sie in dem Zustand ab.
2. Wir verändern das Band gemäß der original Übergangsfunktion.
3. Wir stellen den Zeiger der Einbandturingmaschine wieder vor den ersten im Band kodierten Zeiger.

Kosten für die Simulation:
Die Anzahl der Konfigurationswechsel der simulierenden DTM $\tau'$ ist beschränkt durch ein konstantes Vielfaches der Anzahl der Bandquadrate, die die zu simulierende DTM $\tau$ benutzt. Es gilt:

$\begin{displaymath}T_{\tau '}(n)=C\cdot M_{w}\cdot N_{w}\end{displaymath}$

wobei $M_{w}$ die Konfigurationswechsel der Original-DTM sind und $N_{w}$ die Anzahl der Bandquadrate, die besucht wurden, sowie eine Konstante ist. Es folgt: $\Rightarrow$

$\begin{displaymath}T_{\tau '}(n)=O(T_{\tau}(n)^{2})\,,\,wegen\,M_{w}\cdot N_{w}\end{displaymath}$

Es gilt auch

$\begin{displaymath}S_{\tau '}=O(S_{\tau}(n))\,,\,weil\,nur\,hin\,und\,her\,gespult\,wird.\end{displaymath}$

Programmierung von DTMs

Hintereinanderschaltung $f_{\tau_{1};\tau_{2}}=f_{\tau_{1}}\circ f_{\tau_{2}}=f_{\tau_{2}}(f_{\tau_{1}})$
Man vereinigt beide Zustandsmengen⁶. Alle Endzustände der ersten DTM $\tau_{1}$ ersetzt man durch normale Zustände. Wird ein solcher Zustand erreicht, so leitet die DTM in die Zustandsmenge der zweiten DTM $\tau_{2}$ über:

$\begin{displaymath}\delta(q_{F_{\tau_{1}}},a)=(q_{0_{\tau_{2}}},a,N)\end{displaymath}$

Schleifen, bedingte Anweisungen usw.
Wir konstruieren eine DTM, die die Bedingung überprüft. Abhängig von der Ausgabe dieser DTM führen wir in die eine oder die andere DTM mit Hilfe des Zustandsmengenwechsels über.
Unterprogramme
Es gibt Zustände, in denen Kontrollinformationen mitgespeichert werden (z.B. Rücksprungadressen). Lokale Variablen von Unterprogrammen können auf einem Extraband gespeichert werden. Die wirft jedoch Probleme bei der Rekursion auf. Besser ist es, sie nacheinander an Stellen des zweiten Bandes zu speichern und sie mit entsprechenden Sonderzeichen von anderen Unterprogrammvariablen zu trennen.

Fußnoten

... Turingmaschine ⁴: Man schreibt leicht ,,Touringmaschine''. Aber Turingmaschinen kommen gar nicht auf Touren, sondern sie sind einfach nur Turingmaschinen ohne o.
... ausgeführt ⁵: Die Zustände haben die Form $<q,b_{1},b_{2},\ldots,b_{k},c,\ldots>$ , wobei $b_{i}\in \Gamma\cup\{?\}$ . Das ,,'' steht dafür, daß das Zeichen auf dem betreffenden Band noch nicht bekannt ist
... Zustandsmengen ⁶: Dabei darf natürlich dann kein Zustand mit selben Namen einmal überschrieben werden.

Nächste Seite: Registermaschine Turingmaschine Aufwärts: Berechenbarkeit Vorherige Seite: Registermaschinen (kurz: RM) Inhalt