Eines der grundlegendsten Berechnungsmodelle in der Informatik sind die Turingmaschinen. Diese werden benutzt, um maschinelle Berechnungen zu formalisieren und darüber strukturiert zu argumentieren. Sie können daher als ein mathematisch fundiertes Modell eines Computers angesehen werden.
In dieser Unit werden wir lernen, wie eine Turingmaschine definiert ist, wobei wir versuchen, sowohl formales als auch intuitives Wissen gleichermaßen zu fördern. Weiterhin befassen wir uns mit der Semantik der Turingmaschine, das heißt, wie sie auf Eingaben arbeitet und wann sie erfolgreich terminiert.
Historisches
Geschichtlich gesehen geht die Turingmaschine auf Alan Turing zurück, der als einer der Begründer der modernen Wissenschaft Informatik angesehen wird. Jüngst wurde er durch den Film The Imitation Game populär. Er hat Turingmaschinen bereits 1936 definiert, zu einer Zeit, als es noch keinerlei Computer gab, wie wir sie heute kennen. Demzufolge mutet die Definition auf den ersten Eindruck ein wenig seltsam an. Oft fühlen sich Modelle wie WHILE, GOTO oder LOOP intuitiver an, weil sie modernen Programmiersprachen entlehnt sind.
Nichtsdestotrotz sind Turingmaschinen immer noch das am weitesten verbreitete Modell in der theoretischen Informatik. Dies hat mehrere Gründe:
Die meisten theoretischen Resultate existieren für Turingmaschinen, aber nicht für WHILE, GOTO etc. Weiterführende Forschung baut daher auf Turingmaschinen auf.
Turingmaschinen sind genauso mächtig wie WHILE, GOTO, \(\mu\)-Rekursion und viele andere Modelle.
Die Konfiguration einer Turingmaschine kann sehr kompakt beschrieben werden.
Platzkomplexität auf Turingmaschinen ist sehr einfach zu definieren (im Gegensatz zu WHILE oder GOTO).
Definition
Die formale Definition einer Turingmaschine kann auf den ersten Blick sehr technisch aussehen, was oft Schwierigkeiten bereitet. Die Intuition dahinter ist jedoch vergleichsweise einfach. Auf die intuitive Arbeitsweise einer Turingmaschine wird in dem folgenden Video eingegangen.
In dem Video wurde die Turingmaschine auf einem Band eingeführt. Allgemeiner ist es, wenn man \(k\) Bänder verwendet, da einige Operationen (zum Beispiel kopieren) auf \(\geq 2\) Bändern effizienter sind. Dazu muss man lediglich die Übergangsfunktion anpassen.
Wir halten fest: Eine \(k\)-Band Turing-Maschine ist ein Tupel \(M = (Q, \Sigma, \square, q_0, F, \delta)\), wobei
\(Q\) eine endliche, nichtleere Menge an Zuständen,
\(\Sigma\) eine endliche, nichtleere Menge an Symbolen für das Eingabealphabet,
\(\square \in \Sigma\) das Blank-Symbol (einziges Symbol, das unendlich oft auf dem Band stehen darf),
\(q_0 \in Q\) der Startzustand,
\(F \subseteq Q\) die akzeptierenden Zustände und
\(\delta \colon (Q \times \Sigma^k) \longrightarrow (Q \times \Sigma^k \times \{ L, S, R\}^k)\) eine partielle Funktion namens Übergangsfunktion ist.
Hast du verstanden, wie Turingmaschinen funktionieren? Dann versuche herauszufinden, was die folgende Turingmaschine macht:
Die Turingmaschine ist relativ simpel: Sie testet einfach, ob die Eingabe nur aus 0 besteht, und erreicht in dem Fall den Zustand yes. Anderenfalls endet sie im Zustand no.
Semantik von Turingmaschinen
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.
Anmerkung: Mit der obigen Definition für Speicher ist es nicht möglich, einen sublinearen Speicherverbrauch zu erreichen, da die Eingabe zu Beginn immer auf dem Band steht und damit schon zu Buche schlägt. Das ist unschön. Daher definiert man für gewöhnlich den Platzverbrauch für Turingmaschinen mithilfe einer \(2\)-Band-Maschine. Das erste Band beinhaltet die Eingabe und kann nur gelesen werden. Das zweite Band darf hingegen nach Belieben benutzt werden. In diesem Falle wird der Platzverbrauch dann als der maximale Bandinhalt bezüglich des zweiten Bandes definiert. Effektiv wird also die Größe der Eingabe ignoriert und nur zusätzlicher Speicherverbrauch gezählt.
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.
