Wir halten fest: Eine Konfiguration ist eine Momentaufnahme einer Turingmaschine. Wenn man eine Konfiguration hat, kann man bestimmen, ob eine Turingmaschine \(M\) darauf hält, akzeptiert oder eben nicht. Man kann es ein bisschen damit vergleichen, dass man den Speicher und die Line of Code von einem Programm bekommt (aber interessanterweise nicht das Programm selbst!).
Formal ist eine Konfiguration einer \(1\)-Band-Turingmaschine 1 ein Wort \(w \in \Sigma^* Q \Sigma^*\). Dabei interpretieren wir \(w = \alpha q \beta\) so, dass \(\alpha\beta\) auf dem Band steht, die Turingmaschine in Zustand \(q\) ist und der Lese/Schreib-Kopf auf das erste Zeichen von \(\beta\) zeigt. Die Übergangsfunktion \(\delta\) der Turingmaschine \(M\) definiert uns dann intuitiv die Übergangsrelation \(\vdash \subseteq (\Sigma^* Q \Sigma^*) \times (\Sigma^* Q \Sigma^*)\) wie folgt.
$$ a_1 \ldots a_m q b_1 \ldots b_n \vdash \begin{cases}
a_1 \ldots a_m q' c b_2 \ldots b_n \ &\text{ falls } \delta(q,b_1) = (q', c, S) \text{ und } m \geq 0, n \geq 1 \\
a_1 \ldots a_m c q' b_2 \ldots b_n \ &\text{ falls } \delta(q,b_1) = (q', c, R) \text{ und } m \geq 0, n \geq 2 \\
a_1 \ldots a_{m-1} q' a_m c b_2 \ldots b_n \ &\text{ falls } \delta(q,b_1) = (q', c, L) \text{ und } m \geq 1, n \geq 1
\end{cases}$$
Zwei Fälle müssen gesondert betrachtet werden: Falls die Turingmaschine mit ihrem Lese/Schreib-Kopf an eine bisher nicht gesehene Position läuft, muss die Konfiguration dementsprechend angepasst werden.
Damit lässt sich nun auch sinngemäß die Berechnung einer Turingmaschine definieren. Wir sagen, dass eine Turingmaschine \(M = (Q, \Sigma, \square, q_0, F, \delta) \) eine Eingabe \(x\) akzeptiert, falls es \(\alpha, \beta \in \Sigma^*\) und ein \(q \in F\) gibt, sodass
$$q_0 x \vdash \ldots \vdash \alpha q \beta,$$
und es keine weitere Konfiguration \(w\) gibt, sodass
$$\alpha q \beta \vdash w.$$
Die letzte Eigenschaft bedeutet, dass die Turingmaschine hält, d. h., dass es keine weiterführende Konfiguration gibt. Mit \(q \in F\) stellen wir sicher, dass die Turingmaschine in einer akzeptierenden Konfiguration (siehe Definition) hält. Anderenfalls sagen wir, dass die Turingmaschine nicht akzeptiert. Es ist aber auch möglich, dass eine Turingmaschine auf einer Eingabe eine endlose Folge von Konfigurationen besucht. In dem Fall sagen wir, dass die Turingmaschine divergiert bzw. nicht hält.
Schlussendlich können wir damit die Semantik einer Turingmaschine definieren. Wir definieren die Funktion
$$L(M) := \{ x \mid M \text{ akzeptiert Eingabe } x \}$$
und sagen dann, dass \(M\) eine Sprache \(L(M)\) erkennt.
Alles verstanden? Dann teste dein Wissen! Welche Sprache erkennt die folgende Turingmaschine? Versuche erst herauszufinden, was die Turingmaschine mit einer Eingabe macht, und stelle dann eine generelle Regel auf, wann die Turingmaschine ein Wort akzeptiert und wann nicht.
Die Turingmaschine akzeptiert alle Palindrome gerader Länge.
Laufzeit und Speicher
Mit Hilfe der Konfigurationen lässt sich nun sehr einfach die Laufzeit und der Speicherverbrauch einer Turingmaschine definieren. Wir sagen \(\mathrm{Time}_M(x)\) ist Anzahl an Konfigurationen, die eine Turingmaschine \(M\) auf Eingabe \(x \in \Sigma^*\) durchläuft, bevor sie hält.
Gegeben ein \(n \in \mathbb N\) definieren wir dann die Zeitkomplexität von \(M\) als
$$\mathrm{Time}_M(n) := \max\{ \mathrm{Time}_M(x) \mid |x| = n\}.$$
Ähnlich einfach lässt sich die Platzkomplexität definieren. Seien \(C_1 \vdash C_2 \vdash \ldots \) die Konfigurationen, die eine Turingmaschine \(M\) auf Eingabe \(x\in\Sigma^*\) durchläuft. Wir definieren \(\mathrm{Space}_M(x) := \max \{|C_1|, |C_2|, \ldots\} \). Falls die Turingmaschine nicht hält, bilden wir das Maximum über (abzählbar) unendlich viele Konfigurationen.
Für ein \(n \in \mathbb N\) schreiben wir dann
$$\mathrm{Space}_M(n) := \max\{ \mathrm{Space}_M(x) \mid |x| = n\}.$$
In anderen Worten ist also \(\mathrm{Time}_M(n)\) und \(\mathrm{Space}_M(n)\) die Worst-Case Laufzeit bzw. Platzverbrauch, die die Turingmaschine \(M\) auf eine Eingabe der Länge \(n\) haben kann.
Was haben wir gelernt?
Turingmaschinen sind ein beliebtes Berechnungsmodell.
Sie benutzen Zustände und Zustandsübergänge, um auf einer Eingabe zu arbeiten.
Eine vollständige Beschreibung eines Berechnungsschrittes ist eine Konfiguration. Konfigurationen können benutzt werden, um Berechnungen formal zu definieren.
Eine Turingmaschine erkennt eine Sprache \(L\). Dies ist genau die Menge aller Wörter \(x\), sodass \(x\) von \(M\) akzeptiert wird.
Man kann kanonisch Platzverbrauch und Laufzeit einer Turingmaschine an ihren Konfigurationen ablesen.
1Für \(k\)-Band-Turingmaschinen ist eine ähnliche Definition möglich, da sie aber nicht viel zum Verständnis beiträgt, verweisen wir dafür auf bekannte Textbücher.↩
Algorithm Engineering
Our research focus is on theoretical computer science and algorithm engineering. We are equally interested in the mathematical foundations of algorithms and developing efficient algorithms in practice. A special focus is on random structures and methods.
