All posts by fgi1

P und NP

Posted On 10 Dez 2014
By fgi1
In Uncategorized

Wir haben in dem vorherigen Abschnitt definiert, wie die Zeit- und die Platzkomplexität einer Turingmaschine bestimmt werden kann. Betrachtet man nun Polynome als Schranken, d.h. nimmt man z.B. $p(n) = n^2$ und betrachtet nun die Sprachen, die von Turingmaschinen akzeptiert werden, die bei einer Eingabe der Länge $n$ maximal $n^2$ viele Schritte tätigen dürfen, so gelangt man zur Komplexitätsklasse $P$, die wir ebenfalls schon im letzten Abschnitt gesehen haben. Die Komplexitätsklasse $P$ umfasst gerade jene Sprache $L$, die von einer deterministischen Turingmaschine $M$ akzeptiert werden können, deren Laufzeit durch ein Polynom beschränkt ist. Entsprechend wird die Komplexitätsklasse $NP$ mittels nichtdeterministischer Turingmaschinen eingeführt. Wir wiederholen die Definition von $P$ und $NP$ hier einmal.

Definiton 5.2.1 (Die Klassen P und NP)

Wir definieren die Komplexitätsklassen $P$ und $NP$. Sie enthalten Probleme, die von einer deterministischen bzw. einer nichtdeterministischen Turingmaschine mit einer polynomiellen Zeitschranke akzeptiert werden können.
\begin{eqnarray*}
P & := & \{L \mid \text{es gibt ein Polynom $p$ und eine} \\
& & \quad \text{$p(n)$-zeitbeschränkte DTM $A$ mit $L(A) = L$}\} \\
& = & \cup_{i \geq 1} DTIME(n^i) \\
NP & := & \{L \mid \text{es gibt ein Polynom $p$ und eine} \\
& & \quad \text{$p(n)$-zeitbeschränkte NTM $A$ mit $L(A) = L$}\} \\
& = & \cup_{i \geq 1} NTIME(n^i)
\end{eqnarray*}

Die Komplexitätsklassen $P$ und $NP$ sind im Grunde Sprachfamilien (d.h. Mengen von Sprachen). Die Sprachen, die in $P$ bzw. $NP$ enthalten sind, sind aber gerade über Komplexitätsmaße definiert. Daher die Bezeichnung Komplexitätsklassen.

In der Definition von $P$ wird nur gefordert, dass $L$ von einer DTM $A$ akzeptiert wird. Die Sprache ist also aufzählbar. Tatsächlich können die Sprachen aber auch entschieden werden. Die Kernidee ist, die Turingmaschine zunächst $p(n)$ ausrechnen zu lassen und dann einen Zähler bei jedem Schritt zu erhöhen. Erreicht man die $p(n)$ und hat noch nicht akzeptiert, so kann abgelehnt werden. Wir führen dies noch einmal aus.

Satz 5.2.2

\begin{eqnarray*}
P & = & \{L \mid L \text{ wird von einem Algorithmus} \\
& & \quad \text{in Polynomialzeit entschieden}\}
\end{eqnarray*}

Beweis

Die Richtung von rechts nach links ist klar, denn wenn $L$ in Polynomialzeit entschieden wird, dann wird es auch in Polynomialzeit aufgezählt und damit ist es in $P$. Es ist nun also zu zeigen, dass jede in Polynomialzeit akzeptierbare Sprache auch in Polynomialzeit entscheidbar ist. Sei $A$ ein Algorithmus der $L$ in Zeit $O(n^k)$ akzeptiert. Es gibt dann eine Konstante $c$, so dass $A$ die Sprache in höchstens $c \cdot n^k$ Schritten akzeptiert. Ein Algorithmus $A‘$, der $L$ entscheidet, berechnet bei Eingabe $x$ zunächst $s = c \cdot |x|^k$ und simuliert $A$ dann $s$ Schritte lang. Hat $A$ akzeptiert, so akzeptiert auch $A‘$, hat $A$ bisher nicht akzeptiert, so lehnt $A‘$ die Eingabe ab. Damit entscheidet $A‘$ die Sprache $L$ in $O(n^k)$.

Die Klasse $P$ ist deswegen von besonderer Bedeutung, weil man davon ausgeht, dass Probleme, die in $P$ liegen effizient gelöst werden können. Dies ist natürlich nur eine auf Intuition basierende Aussage und bestimmt ist ein Algorithmus mit einer Laufzeit von $n^{100}$ kein effizienter Algorithmus und ein Algorithmus mit einer Laufzeit von $2^{(n/10^{50})}$ dürfte für die allermeisten Anwendungen sehr effizient sein. Aus Erfahrung weiß man aber, dass solche Laufzeiten faktisch nicht oder nur bei konstruierten Beispielen auftreten. In der Praxis hat sich die Merkregel „Problem ist in $P$ bedeutet, das Problem ist effizient lösbar“ bewährt.

Ein typisches Problem in $P$ ist z.B. die Frage nach einem kürzesten Pfad in einem Graphen
$$ \texttt{PATH} = \{\langle G,s,t,k \rangle \mid
\begin{array}{l}
G = (V,E) \text{ ist ein ungerichteter Graph,} \\
s,t \in V, \\
k \geq 0 \text{ ist eine ganze Zahl und} \\
\text{es existiert ein $s$–$t$-Pfad in $G$,} \\
\text{der aus höchstens $k$ Kanten besteht.}
\end{array}\} $$

Obige Formulierung sucht nicht nach einem kürzesten Pfad, sondern ist das zugehörige Entscheidungsproblem. Wir haben aber in dem vorherigen Abschnitt besprochen, wie man zu einem Entscheidungsproblem das zugehörige Optimierungsproblem löst und andersherum. Hier würde man für fallende $k$ immer wieder das Entscheidungsproblem starten und so das Optimierungsproblem lösen.

Wandelt man dieses Problem nun geringfügig ab und sucht nicht nach einem kürzesten Pfad, sondern nach einem längsten Pfad, so wird das Problem deutlich komplizierter und scheint tatsächlich nicht mehr in $P$ zu liegen:
$$ \texttt{PATH} = \{\langle G,s,t,k \rangle \mid
\begin{array}{l}
G = (V,E) \text{ ist ein ungerichteter Graph,} \\
s,t \in V, \\
k \geq 0 \text{ ist eine ganze Zahl und} \\
\text{es existiert ein $s$–$t$-Pfad in $G$,} \\
\text{der aus mindestens $k$ Kanten besteht.}
\end{array}\} $$

In $NP$ liegt dieses Problem aber ganz bestimmt, denn wir können mit einer nichtdeterministischen Turingmaschine alle Pfade zwischen $s$ und $t$ raten und dann prüfen, ob ein Pfad der Länge $k$ enthalten ist.

Etwas anderes ist hier aber auch auffällig. Während es zwar schwierig zu sein scheint eine Lösung für $\texttt{L-PATH}$ zu berechnen, so kann, gegeben ein Pfad, schnell überprüft werden, ob dies eine Lösung ist. Diese Überlegung führt zu einer alternativen Beschreibung von $NP$. Wir definieren dazu zunächst einen Verifikationsalgorithmus. Dieser erhält zwei Eingaben. Die eigentliche Probleminstanz $x$ und eine weitere Zeichenkette $y$, Zertifikat genannt. Der Algorithmus prüft dann, ob $y$ eine Lösung der Probleminstanz $x$ ist.

Definiton 5.2.3 (Verifikationsalgorithmus)

Ein Verifikationsalgorithmus $A$ ist ein deterministischer Algorithmus mit zwei Argumenten $x,y \in \Sigma^*$, wobei $x$ die gewöhnliche Eingabe und $y$ ein Zertifikat ist. $A$ verifiziert $x$, wenn es ein Zertifikat $y$ gibt mit $A(x,y) = 1$. Die von $A$ verifizierte Sprache ist
$$ L = \{ x \in \{0,1\}^* \mid \exists y \in \{0,1\}^*: A(x,y) = 1\}. $$

Man beachte, dass auch in diesem Fall die $x$ die Sprache ausmachen. Das Zertifikat $y$ kann vom Algorithmus $x$ genutzt werden, um zu entscheiden, ob $x \in L$ gilt oder nicht.

Die Klasse $NP$ kann nun auch beschrieben werden, in dem man verlangt, dass ein Verifikationsalgorithmus mit polynomieller Laufzeit existiert. Zusätzlich verlangt man, dass $y$ nur eine polynomielle Länge in $x$ hat.

Definiton 5.2.4 (NP (alternative Definition)

$L \in NP$ gdw. ein Verifikationsalgorithmus $A$ mit zwei Eingaben und mit
polynomialer Laufzeit existiert, so dass für ein $c$
$$ L = \{ x \in \{0,1\}^* \mid
\begin{array} {l}
\text{es existiert ein Zertifikat $y$ mit $|y| \in O(|x|^c)$,} \\
\text{so dass $A(x,y) = 1$ gilt}
\end{array}\} $$
gilt.

Mehr zum Verifikationsalgorithmus und zu NP

Betrachten wir die Definition noch einmal genauer. Ein Problem ist in $NP$, wenn ein Verifikationsalgorithmus existiert, der $L$ akzeptiert. Soweit so gut. Ein Verifikationsalgorithmus unterscheidet sich von einem ``normalen'' Algorithmus dadurch, dass er neben der Instanz $x$ des Problems, das er lösen soll, noch eine zusätzliche Eingabe $y$ erhält. Dieses $y$, das Zertifikat, soll ihm helfen, zu entscheiden, ob er $x$ akzeptieren soll oder nicht. Betrachten wir z.B. das Erfüllbarkeitsproblem der Aussagenlogik. Die Eingabeinstanz ist eine Formel $F$, das Zertifikat könnte dann eine (erfüllende) Belegung sein. Der Verifikationsalgorithmus überprüft dann lediglich, ob die Belegung tatsächlich eine erfüllende ist. Um $NP$ zu erfassen darf man nun nicht einen uneingeschränkten Verifikationsalgorithmus nehmen, da man damit dann zu viel könnte. Der Verifikationsalgorithmus darf nur eine polynomielle Laufzeit haben. Ferner darf $y$ nur polynomiell in der Länge von $x$ sein. Z.B. könnte es sein, dass $y$ nur maximal von der Länge $|x|^2$ sein darf. Warum diese Einschränkung? Sonst wird das Zertifikat wieder zu mächtig und außerdem könnte man sonst eine deutlich längere Laufzeit im Vergleich mit $x$ haben. Ist $y$ nämlich deutlich länger als $x$, also z.B. exponentiell in $|x|$, dann arbeitet der Verifikationsalgorithmus zwar vielleicht polynomiell in der Länge von $x$ und $y$, was dann aber exponentiell in der Länge von $x$ sein kann (da $y$ ja so lang ist) und dies könnte der nichtdeterministische Algorithmus dann nicht mehr schaffen (siehe die nachfolgende Konstruktionsidee). Ist außerdem das Zertifikat länger als polynomiell in $x$, so kann es von einer nichtdeterministischen, polynomialzeitbeschränkten Turingmaschine nicht geraten werden, da diese ja nur polynomiell viele Schritte in der Länge von $x$ machen darf (siehe ebenfalls die nachfolgende Konstruktionsidee).

Wir haben oben gesagt, dass wir $NP$ alternativ mittels der Verifkationsalgorithmen definieren. Streng genommen würde man sagen, dass eines die Definition ist und dann von der zweiten zeigen, dass sie zur ersten äquivalent ist. Wir wollen dies hier nicht im Detail machen, sondern einfach mit beiden Formulierungen als Definition arbeiten.

Warum sind die beiden Definitionen äquivalent?

Es lohnt sich aber, sich kurz zu überlegen, warum die beiden Definitionen äquivalent sind. Die Kernidee ist die folgende: Ein nichtdeterministischer Algorithmus kann Werte raten. Eine bestimmte Folge dieser geratenen Werte führt dann zum Erfolg. Ein Zertifikat kann dann gerade aus den richtigen dieser geratenen Werte bestehen. Betrachten wir z.B. das folgende Mengenpartitionsproblem:

Gegeben sei eine Menge $S \subseteq \mathbb{N}$. Gesucht ist eine Menge $A \subseteq S$, so dass $\sum_{x \in A} x = \sum_{x \in \overline{A}} x$ gilt.

Ein nichtdeterministischer Algorithmus rät für jedes Element aus $S$, ob es in $A$ sein soll oder nicht und überprüft dann, ob die beiden Summen identisch sind. Ein Verifikationsalgorithmus erhält als Zertifikat gerade die Elemente der Menge $A$ und prüft dann, ob die Summe stimmt. Wenn es eine Menge $A$ gibt, mit der dies klappt, so wird der nichtdeterministische diese raten und für den Verifikationsalgorithmus gibt es diese als Zertifikat.

Wir kennen nun zwei Darstellungen für $NP$. Will man nun also zeigen, dass ein Problem in $NP$ ist, so kann man entweder zeigen, dass es eine nichtdeterministische Turingmaschine gibt, die dieses Problem in Polynomialzeit löst oder man kann zeigen, dass es einen Verifikationsalgorithmus gibt, der in Polynomialzeit arbeitet und das Problem löst. Beides genügt zwar, um zu zeigen, dass das Problem in $NP$ ist. Wenn man ein solche Problem aber in der Praxis lösen will, dann hilft das so nicht viel, denn man kann ja weder eine nichtdeterministische Maschine bauen, noch einen Verifikationsalgorithmus entwerfen (denn wo sollte das Zertifikat herkommen?). Wie also löst man ein solches Problem deterministisch?

Pause to Ponder: Wie löst man ein $NP$-Problem mit einer deterministischen Turingmaschine?

Tatsächlich haben wir dieses Problem schon gelöst. Wir haben ja bereits im vorherigen Kapitel gezeigt, dass jede nichtdeterministische Turingmaschine von einer deterministischen Turingmaschine simuliert werden kann. Dies könnten wir hier also einfach nutzen, um die NTM, die ein Problem aus $NP$ akzeptiert, durch eine DTM zu simulieren und so das Problem deterministisch zu entscheiden. Äquivalent ist die Überlegung jedes mögliche Zertifikat durchzuprobieren. Man beachte hierfür, dass die Zertifikate in der Länge beschränkt sind. Es kann also nur endlich viele geben. Dies ist allerdings sehr aufwändig, da es sehr viele Zertifikate einer Länge $k$ geben kann (hat man $m$ Symbole, so gibt es dann $m^k$ Zeichenketten, die im schlimmsten Fall alle probiert werden müssen). Die Simulation einer NTM ist allerdings auch sehr teuer. Im Grunde genommen sind beides Brute-Force-Methoden, bei denen alle Möglichkeiten durchprobiert werden — alle Rechnungen der NTM oder eben alle Zertifikate. Dies ergibt eine obere Schranke für einen deterministischen Algorithmus, der ein $NP$-Problem löst.

Satz 5.2.5

Sei $L \in NP$, dann gibt es ein $k \in \mathbb{N}$ und einen deterministischen Algorithmus, der $L$ in $2^{O(n^k)}$ entscheidet.

Beweis

Beweisskizze/Idee: Ist $L \in NP$, so gibt es einen Verifikationsalgorithmus in $O(n^k)$ ([/latex]n[/latex] ist die Eingabelänge). Das Zertifikat $y$ hat eine Länge in $O(n^c)$. Man geht alle $2^{O(n^c)}$ Zertifikate durch und führt für jeden den Verifikationsalgortihmus aus. Dieses Verfahren ist (unter der sinnvollen Annahme $k > c$) in $2^{O(n^k)}$.

Mehr zur Laufzeitschranke

Will man hier genauer sein, so müsste man zunächst sagen, dass das Verfahren eigentlich in $2^{O(n^c)} \cdot O(n^k)$ ist. Wegen $n^k \leq 2^{n^k}$ kann man dies nach oben mit $2^{O(n^c)} \cdot 2^{O(n^k)}$ abschätzen. Nun darf man $k \geq c$ annehmen, da sonst der Verifikationsalgorithmus eine Laufzeit hätte bei der er sich gar nicht das ganze Zertifikat ansehen kann. Damit kann man nach oben durch $2^{O(n^k)} \cdot 2^{O(n^k)}$ abschätzen. Dies ist gleich $2^{2 \cdot O(n^k)} = 2^{O(n^k)}$.

Definiton 5.2.6 (Typische NP-Probleme)

Die folgenden Probleme sind typische Beispiele für Problem in $NP$.

Name: Mengenpartitonsproblem
Gegeben: Eine endliche Menge $S \subseteq \mathbb{N}$
Frage: Gibt es eine Menge $A \subseteq S$, so dass $\sum_{x \in A} x = \sum_{x \in \overline{A}} x$ gilt?
Name: Teilsummenproblem
Gegeben: Eine endliche Menge $S \subset \mathbb{N}$ und ein $t \in \mathbb{N}$.
Frage: Gibt es eine Menge $S‘ \subseteq S$ mit $\sum_{s \in S‘} s = t$?
Name: Cliquenproblem
Gegeben: Ein ungerichteter Graph $G = (V,E)$ und ein $k \in \mathbb{N}$.
Frage: Enthält $G$ eine Clique, d.h. ein vollständigen Graphen, der Größe $k$ als Teilgraph?
Name: Färbungsproblem
Gegeben: Ein ungerichteter Graph $G = (V,E)$ und ein $k \in \mathbb{N}$.
Frage: Kann $G$ mit $k$ Farben gefärbt werden? D.h. gibt es eine Funktion
$c : V \rightarrow \{1, \ldots, k\}$ derart, dass $c(u) \not= c(v)$ für jede Kante $\{u,v\} \in E$ gilt?

Alle oben genannten Probleme sind in $NP$ und damit schnell nichtdeterministisch lösbar. Die besten bekannten deterministischen Algorithmen arbeiten allerdings im Grunde so wie oben im allgemeinen Fall illustriert mit einer Brute-Force-Methode und benötigen daher expoentielle Laufzeit.

Hinweis

Die Aussage stimmt nicht ganz, da mittlerweile für etliche $NP$-Probleme auch etwas bessere Algorithmen bekannt sind. Diese Algorithmen sind allerdings weiterhin exponentiell, so dass die generelle Aussage gültig bleibt. Aus Praxissicht sind diese Algorithmen dann aber immerhin etwas besser als die Brute-Force-Methode und tatsächlich ist es ein aktives Foschungsfeld hier Algorithmen zu entwickeln, die mit immer größeren Eingabeinstanzen fertig werden.

Die Frage ist nun, geht es wirklich nicht schneller? Wenn wir dies beantworten könnten, so könnten wir entweder versuchen schnellere Algorithmen zu entwerfen oder können dies ohne schlechtes Gewissen unterlassen. Um die Suche nach unteren Schranken soll es im nächsten Abschnitt zur $NP$-Vollständigkeit gehen.

Zeit- und Platzkomplexität

Posted On 9 Dez 2014
By fgi1
In Uncategorized

Download PDF

Wir werden in diesem Abschnitt die Zeit- und Platzkomplexität einer Rechnung einer Turingmaschine einführen. Um dies formal machen zu können, benötigen wir zunächst den Begriff der Größe einer Probleminstanz, denn die Zeit, die für eine Berechnung benötigt wird, darf mit Sicherheit von der Größe des Problems abhängen. Um z.B. $10$ Zahlen zu sortieren, wird man i.A. nicht so lange brauchen wie für das Problem, eine Million oder eine Milliarde Zahlen zu sortieren.

Für eine Turingmaschine ist eine Probleminstanz einfach eine Eingabe $w$ und die Größe der Probleminstanz ist dann die Länge von $w$, also $|w|$. Will man z.B. Zahlen addieren, so ist dies als Sprache $L = \{ \langle x,y,z \rangle \mid x+y = z\}$. Eine Probleminstanz ist dann ein Tripel $(2,3,5)$ („Ja“-Instanz, da eine Turingmaschine für $L$ dieses Tripel akzeptieren würde) oder $(2,3,6)$ („Nein“-Instanz, da eine Turingmaschine für $L$ dieses Tripel ablehnen würde). Die Größe einer Probleminstanz ist nun die Länge der Eingabe. Für eine Turingmaschine müsste man die Zahlen noch (bspw. als Binärzahlen) kodieren ebenso wie das Tupel. Die Länge der Eingabe wächst dann entsprechend.

Wir definieren nun den Zeit- und Platzbedarf, den eine Turingmaschine bei einer Rechnung auf einer Eingabe hat und damit dann Zeit- und Platzbeschränktheit.

Definiton 5.1.1 (Zeit- und Platzkomplexität einer deterministischen Turingmaschine)

Sei $M$ eine deterministische Turingmaschine. Sei $w$ ein Eingabewort.

Für eine Rechnung auf $w$ benötigt $M$ so viel Zeit, wie in der Rechnung einzelne Konfigurationen durchlaufen werden.
$M$ benötigt in einer Rechnung auf $w$ soviel Platz, wie verschiedene Felder besucht werden.

Seien nun $t,s$ Funktionen von $\mathbb{N}$ nach $\mathbb{R}$. Eine DTM $M$ ist

$t(n)$–zeitbeschränkt genau dann, wenn
\begin{eqnarray*}
t(n) & \geq & \max\{k \mid \exists w \in L(M): n = |w| \text{ und} \\
& & \quad \text{$M$ akzeptiert in $k$ Schritten} \}
\end{eqnarray*}
$s(n)$–platzbeschränkt genau dann, wenn
\begin{eqnarray*}
s(n) & \geq & \max\{k \mid \exists w \in L(M): n = |w| \text{ und} \\
& & \quad \text{$M$ akzeptiert mit Platzbedarf $k$} \}
\end{eqnarray*}

Man beachte, dass alle Eingaben der Länge $n$ betrachtet werden und dann $t(n)$ mindestens so groß sein muss, wie der Zeitbedarf im schlimmsten Fall (analog für den Platzbedarf und $s(n)$). Man bezeichnet die oben definierten Komplexitätsmaße daher als worst-case-Komplexitäten.

Noch zwei Anmerkungen zur Definition. Die Funktionen $t$ und $s$ sind nur deswegen Abbildungen auf die reelle Zahlen, damit wir später mit Funktionen wie $n^2 + n/2$ arbeiten können, die ja nicht bei jedem $n \in \mathbb{N}$ eine natürliche Zahl liefern. Ferner werden oft Anfangswerte ignoriert und man erlaubt auch z.B. $t(n) = n^2 – 5 \cdot n$, was erst ab $n \geq 4$ einen sinnvollen Wert ergibt. Außerdem rundet man $t(n)$ und $s(n)$ ab, um auch Brüche u.ä. zu erlauben.

Beispiel

Hat eine deterministische Turingmaschine bspw. die Rechnung $$ z_0 ab \vdash Az_1 \vdash ABz_2 \# \vdash ABX z3 \# \vdash ABz_3 X $$ so werden für diese Rechnung $5$ Zeiteinheiten benötigt und $4$ Felder benutzt (das vierte Feld wird nicht geändert und bleibt leer, es wurde aber besucht und zählt daher).

Ist eine DTM $t(n)$-zeitbeschränkt mit $t(n) = n^2 - n/2$, dann darf eine Rechnung auf einem Wort $w$ der Länge $10$ nur maximal $100 - 5 = 95$ Schritte benötigen und auf einem Wort der Länge $3$ nur maximal $9 - 1,5 = 7,5 \approx 7$ Schritte. Für die Zeitbeschränkung wird dann eine möglichst genaue obere Schranke $t$ gesucht.

Warum zählen unbenutzte, aber besuchte Felder?

Der Grund warum Felder sofort bei Besuch zum Platzbedarf zählen und nicht erst, wenn sie beschrieben werden, ist, da man ansonsten mit den leeren Feldern z.B. unnär zählen könnte. So könnte man große Zahlen mit wenig Speicherbedarf (nämlich nur für die Begrenzer) kodieren und hätte später irreführende Aussagen zur Komplexität.

Wir definieren nun ganz entsprechend die Zeit- und Platzkomplexität einer nichtdeterministischen Turingmaschine. Hier muss aber eine Erfolgsrechnung festgehalten werden, da eine NTM auf einem Eingabewort ja (nichtdeterministisch) mehrere verschiedene Rechnungen haben kann.

Definiton 5.1.2 (Zeit- und Platzkomplexität einer nichtdeterministischen Turingmaschine)

Sei $M$ eine nichtdeterministische Turingmaschine. Sei $w$ ein Eingabewort.
In einer fest vorgegebenen Erfolgsrechnung auf $w$

benötigt eine NTM so viel Zeit, wie in der Rechnung einzelne Konfigurationen durchlaufen werden und
soviel Platz, wie verschiedene Felder besucht werden.

Eine NTM $M$ akzeptiert ein $w \in L(M)$ mit

der Zeitbeschränkung $t \in \mathbb{R}$ genau dann, wenn die kürzestes Erfolgsrechnung $\lceil t \rceil$ Schritte hat
der Platzbeschränkung $s \in \mathbb{R}$ genau dann, wenn die Erfolgsrechnung mit dem geringsten Platzbedarf $\lceil s \rceil$ Felder besucht.

Seien $t,s$ Funktionen von $\mathbb{N}$ nach $\mathbb{R}$. Eine NTM $M$ ist

$t(n)$–zeitbeschränkt genau dann, wenn
\begin{eqnarray*}
t(n) & \geq & \max\{k \mid \exists w \in L(M): n = |w| \text{ und} \\
& & \quad \text{$M$ akzeptiert mit Zeitbeschränkung $k$} \}
\end{eqnarray*}
$s(n)$–platzbeschränkt genau dann, wenn
\begin{eqnarray*}
s(n) & \geq & \max\{k \mid \exists w \in L(M): n = |w| \text{ und} \\
& & \quad \text{$M$ akzeptiert mit Platzbeschränkung $k$} \}
\end{eqnarray*}

Die Definitionen bei einer NTM sind sehr ähnlich zu denen einer DTM. Nur werden hier ausschließlich die Erfolgsrechnungen betrachtet und von diesen dann die beste genommen. Dann wird aber wieder die schlechteste hiervon bezüglich verschiedenere Wörter gleicher Länge genommen. Es ist also auch hier eine worst-case-Betrachtung. Der Nichtdeterminismus wird aber zusätzlich zu dem bisherigen nicht nur so betrachtet, dass so geraten wird, dass man zur positiven Antwort kommt, sofern dies möglich ist, sondern dass sogar so geraten wird, dass für die Rechnung der Zeit- und Platzbedarf möglichst gering ist.

Wir werden noch sehen, dass es nicht weiter schlimm ist, dass wir hier (sowohl bei DTMs als auch bei NTMs) vor allem auf Erfolgsrechnung schauen. In den uns interessierenden Fällen (nämlich den gleich folgenden Komplexitätsklassen $P$ und $NP$) kann man die Schranken dann auch für die Nicht-Erfolgsrechnungen einführen. Damit werden wir dann haben:

Eine TM ist $t(n)$-zeitbeschränkt heißt: Ein Wort der Länge $n$ wird nach $t(n)$ Schritten akzeptiert oder abgelehnt.
Eine TM ist $s(n)$-platzbeschränkt heißt: Eine Rechnung auf einem Wort der Länge $n$ benutzt maximal $s(n)$ Bandzellen.

Komplexitätsklassen

Wir führen jetzt Komplexitätsklassen ein. Diese sind ähnlich wie $REG$, $CF$ usw. Sprachfamilien. Mit ihnen werden aber Sprachen bzw. Probleme erfasst, die in einer bestimmten Zeit-/Platzschranke gelöst werden können. War also z.B. die Sprache $a^* b^*$ in der Sprachfamilie $REG$, weil es einen endlichen Automaten gab, der sie akzeptiert, so werden wir sagen, dass eine Sprache dann in bspw. der Komplexitätsklasse $P$ ist, wenn es eine DTM gibt, die die Sprache akzeptiert und $p(n)$-zeitbeschränkt ist, wobei $p$ ein Polynom ist.

Definiton 5.1.3 (Komplexitätsklasse)

Für $s,t : \mathbb{N} \rightarrow \mathbb{R}$ mit $t(n) \geq n+1$ und $s(n) \geq 1$ definieren wir die Komplexitätsklassen
\begin{eqnarray*}
DTIME(t(n)) & := & \{L \mid L = L(A) \text{ für eine} \\
& & \quad \text{$t(n)$-zeitbeschränkte DTM $A$}\} \\
NTIME(t(n)) & := & \{L \mid L = L(A) \text{ für eine} \\
& & \quad \text{$t(n)$-zeitbeschränkte NTM $A$}\} \\
DSPACE(s(n)) & := & \{L \mid L = L(A) \text{ für eine} \\
& & \quad \text{$s(n)$-platzbeschränkte DTM $A$}\} \\
NSPACE(s(n)) & := & \{L \mid L = L(A) \text{ für eine} \\
& & \quad \text{$s(n)$-platzbeschränkte NTM $A$}\}
\end{eqnarray*}

Während obige Komplexitätsklassen sehr allgemein sind ($DTIME(t(n))$ kann ja quasi für jedes $t$ definiert werden), folgen nun die spezieller definierten Komplexitätsklassen $P$ und $NP$ sowie $PSPACE$ und $NPSPACE$. Diese Komplexitätsklassen werden uns vor allem interessieren (insb. $P$ und $NP$) und diese spielen in der Informatik eine besondere, zentrale Rolle.

Definiton 5.1.4 (P, NP, PSPACE und NPSPACE)

\begin{eqnarray*}
P & := & \{L \mid \text{es gibt ein Polynom $p$ und eine} \\
& & \quad \text{$p(n)$-zeitbeschränkte DTM $A$ mit $L(A) = L$}\} \\
NP & := & \{L \mid \text{es gibt ein Polynom $p$ und eine} \\
& & \quad \text{$p(n)$-zeitbeschränkte NTM $A$ mit $L(A) = L$}\} \\
PSPACE & := & \{L \mid \text{es gibt ein Polynom $p$ und eine} \\
& & \quad \text{$p(n)$-platzbeschränkte DTM $A$ mit $L(A) = L$}\} \\
NPSPACE & := & \{L \mid \text{es gibt ein Polynom $p$ und eine} \\
& & \quad \text{$p(n)$-platzbeschränkte NTM $A$ mit $L(A) = L$}\}
\end{eqnarray*}

Wir betonen nach diesen Definitionen noch einmal, dass in einer Komplexitätsklasse Probleme zusammengefasst werden, die in einer bestimmten Zeit- oder Platzschranke gelöst werden können. Ist ein Problem in $P$ heißt das, es gibt ein Polynom $p$, so dass eine DTM existiert, die das Problem mit Zeitschranke $p$ löst (also bei einer Eingabe der Länge $n$ maximal $p(n)$ Schritte benötigt). Analog für die Klasse $NP$ mit einer NTM statt einer DTM. Diese Klassen sind nachfolgend für uns besonders wichtig.

Da eine deterministische Turingmaschine, stets wie eine nichtdeterministische Turingmaschine gesehen werden kann, die den Nichtdeterminismus nie ausnutzt, gilt der folgende Satz.

Satz 5.1.5

Es gilt
\begin{eqnarray*}
DTIME(f) & \subseteq & NTIME(f) \\
DSPACE(f) & \subseteq & NSPACE(f) \\
P & \subseteq & NP \\
PSPACE & \subseteq & NPSPACE
\end{eqnarray*}

Zudem muss auch jede Sprache, die man mit einer Zeitschranke von $t$ lösen kann auch mit einer Platzschranke von $t$ gelöst werden können, denn wenn man nur $t(n)$ viele Schritte macht, kann man auch nur $t(n)$ viele Bandzellen benutzen. Daher gilt $DTIME(f) \subseteq DSPACE(f)$, $NTIME(f) \subseteq NSPACE(f)$, $P \subseteq PSPACE$ und $NP \subseteq NPSPACE$.

Damit haben wir bereits die wichtigsten Komplexitätsklassen zusammen. Bis hierhin haben wir definiert wie viel Zeit und Platz eine Turingmaschine zur Berechnung einer Antwort braucht und darauf aufbauend dann Komplexitätsklassen eingeführt, in denen Probleme zusammengefasst sind, die in bestimmten Zeit- oder Platzschranken gelöst werden können. Insbesondere haben wir die wichtigen Komplexitätsklassen $P$ und $NP$ eingeführt.

Man kann auch Komplexitätsklassen untersuchen, die zugleich eine Zeit- und eine Platzschranke betrachten. Dies wollen wir hier aber nicht vertiefen. Zudem gibt es weitere wichtige Komplexitätsmaße. An Bedeutung gewinnen z.B. aufgrund der aktuellen Architekturen Untersuchungen, die die Anzahl der Prozessoren berücksichtigen. Dazu muss aber erst ein Modell mit mehreren Prozessoren eingeführt werden. Auch dies wollen wir hier nicht vertiefen. In weiterführenden Veranstaltungen und Literatur zu verteilten und parallelen Algorithmen trifft man auf diese.

Wir wollen abschließend noch auf drei Punkte eingehen. Erstens auf den Zusammenhang zwischen Turingmaschinen und realen Computern. Es ist eine ähnliche Aussage wie bei der Church-Turing-These auch für Komplexitätsmaße möglich und dies lässt uns verstehen, dass oben eingeführte Komplexitätsmaße nicht nur von theoretischem Interesse sind, sondern gerade ein Bereich sind, der stark in die Praxis wirkt. Zweitens wollen wir kurz die $O$-Notation (oder Landau-Notation) erwähnen, die uns einige Notationen erleichtern wird. Und drittens wollen wir noch auf Entscheidungs- und Optimierungsprobleme eingehen, da alle Komplexitätsklassen oben ja über Entscheidungsprobleme definiert sind, in der Praxis ja aber viel häufiger Optimierungsprobleme auftreten (so will man oft ja nicht nur wissen, ob ein kürzester Pfad zwischen zwei Punkten in einem Graphen existiert, sondern diesen berechnen).

Turingmaschinen und reale Computer

Bis hierhin haben wir uns mit der Zeit- und Platzkomplexität von Turingmaschinen beschäftigt, die ja durchaus recht weit entfernt scheint von einer gängigen, physikalisch implementierten Computerarchitektur. Wir haben ja aber schon im Abschnitt zur Church-Turing-These gesehen, dass ein Computer eine Turingmaschine simulieren kann und umgekehrt auch eine Turingmaschine einen Computer simulieren kann. Diese Erkenntnis hat zur Übertragung von Unentscheidbarkeitsresultaten von der Turingmaschine auf gängige Computer geführt. Betrachtet man die Konstruktionen, wie eine Turingmaschine einen Computer simuliert und umgekehrt, genauer, so stellt man fest, dass diese Konstruktionen lediglich polynomiellen Mehraufwand erfordern, d.h. wenn ein Computer polynomiell zeitbeschränkt ist, dann arbeitet auch die simulierende Turingmaschine in polynomieller Zeit! Ein Problem bzw. eine Sprache ist also in $P$ unabhängig davon, ob wir einen Algorithmus, der in Polynomialzeit arbeitet, für eine Turingmaschine oder für ein gängiges Rechnermodell angeben. Dies ist einer der Gründe für die herausragende Bedeutung der Komplexitätsklasse $P$ und der Grund, warum sie, ganz entsprechend zu der Art wie wir dies hier für Turingmaschinen gemacht haben, bisweilen, insb. in Algorithmenbüchern, auch direkt mit einer imperativen Programmiersprache als Berechnungsmodell eingeführt wird.

Die erweiterte Church-Turing-These sagt aus, dass diese Simulation in Polynomialzeit nicht nur für Turingmaschinen und gängige Rechnermodelle gilt, sondern für alle sinnvollen deterministischen Rechnermodelle. Dies ist so wichtig, dass wir es noch einmal betonen wollen.

Church-Turing-These: Die Klasse der Turing-berechenbaren Funktionen stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein.

Folgerung: Alle hinreichend mächtigen Berechnungsmodelle sind äquivalent.

Erweiterte Church-Turing-These: Sind $B_1$ und $B_2$ zwei vernünftige Rechnermodelle, so gibt es ein Polynom $p$, so dass $t$ Rechenschritte von $B_1$ bei einer Eingabe der Länge $n$ durch $p(t,n)$ Rechenschritte von $B_2$ simuliert werden können.

Folgerung: Zwei (Turing-)äquivalente Modelle lassen sich mit polynomiellen Mehraufwand ineinander umwandeln.

Damit erhält die Komplexitätsklasse $P$ eine besondere Bedeutung. Jede Sprache, die in $P$ ist, kann mit jedem Berechnungsmodell in Polynomialzeit akzeptiert werden (auch wenn die Polynome unterschiedlich sind). Außerdem kann man statt mit Turingmaschinen bei Algorithmen auch mit gängigen Programmiersprachen argumentieren, so fern einen nur interessiert, ob ein Problem in $P$ ist (und nicht der exakte Zeitbedarf auf einem festen Rechnermodell). Dies zusammen mit der Tatsache, dass man i.A. davon ausgeht, dass in P die Probleme liegen, die wir effizient lösen können, begründet die herausragende Bedeutung von $P$. Letzteres liegt daran, dass Polynome meist sehr verträglich wachsen. So wächst $n^2$ im Vergleich zu $2^n$ für steigende $n$ deutlich langsamer. Bspw. ist $50^2 = 2500$, aber $2^{50}$ bereits mehr als eine Billarde.

O-Notation

Aus der vorherigen Betrachtung wissen wir, wie wichtig die Komplexitätsklasse $P$ und damit Polynome sind. In der Praxis sind die genauen konstanten Faktoren im Polynom aber oft nicht interessant. Ebenso sind oft die Summanden mit kleinerem Exponenten meist nicht von Interesse. So interessiert bei einem Polynom wie $n^3 + 2 \cdot n^2 - 5 \cdot n$ oft nur, dass es sich "grob so verhält wie $n^3$". Um dies zu formalisieren, wird die Landau-Notation oder $O$-Notation eingeführt, die insb. auch in der Algorithmik zum Vergleich verschiedener Algorithmen von großer Bedeutung ist. Wir wollen uns hier nicht näher mit der $O$-Notation beschäftigen und wollen uns nur folgendes merken:

Ist $f(n)$ eine Funktion (z.B. $f(n) = n^2$), dann bedeutet

Die Laufzeit des Algorithmus/der Turingmaschine ist in $O(f(n))$.

dass es eine Konstante $c$ gibt, so dass bei einer Eingabe der Länge $n$ die Turingmaschine/der Algorithmus maximal $c \cdot f(n)$ Schritte macht.

Dies ist deswegen praktisch, da man dann bei einem Algorithmus, der z.B. bei $n$ Zahlen alle Zahlen paarweise miteinander vergleicht, sagen kann, dass er eine Laufzeit in $O(n^2)$ hat, obwohl neben den $n^2$ Vergleichen vielleicht noch Dinge passieren, wie eine Schleifenvariable zu erhöhen und ähnliches. So lange dies nur konstant viele Operationen sind, die pro Vergleich passieren, ist die Laufzeit in $c \cdot n^2$ für eine Konstante $c$ und damit in $O(n^2)$.

Oft benutzt man dann in der Algorithmenanalyse auch nicht mehr die Eingabelänge $n$, sondern eine Kenngröße $n$, aus der sich die eigentliche Eingabelänge leicht ermitteln lässt und die aber i.A. aussagekräftiger ist. Hat man z.B. einen Algorithmus auf Graphen, so nimmt man als Kenngröße oft die Anzahl der Knoten $n$ und die Anzahl der Kanten $m$ und drückt die Laufzeit dann bzgl. dieser Kenngrößen aus.

Entscheidungs- und Optimierungsprobleme

Wir wollen zuletzt noch auf die Ähnlichkeiten zwischen Entscheidungs- und Optimierungsproblemen eingehen. Bei Turingmaschinen interessieren wir uns für die Akzeptanz bzw. das Entscheiden von Sprachen. Bei einer vorgelegten Eingabe, soll die Turingmaschine im Rahmen der Zeitschranke anhalten und positiv oder negativ antworten (in diesem Abschnitt haben wir die Zeitschranken zunächst nur für Erfolgsrechnungen eingeführt, wir werden aber im nächsten Abschnitt sehen, dass wir dies auch für unsere Zwecke auf alle Rechnungen erweitern können). Z.B. erhält man als Eingabe einen Graphen $G$, zwei Knoten $s$ und $t$ und eine Schranke $k$ und die Frage ist, ob ein Pfad von $s$ nach $t$ existiert, der höchstens den Wert $k$ hat. In der Praxis interessiert man sich aber meist mehr dafür, den Wert für $k$ zu optimieren oder den Pfad, von $s$ zu $t$ zu bestimmen. Entscheidungs- und Optimierungsprobleme lassen sich aber meist gut ineinander umwandeln, so dass eine Lösung des einen auch zu einer Lösung des anderen führt. Dass man mit einer Lösung des Optimierungsproblems auch das Entscheidungsproblem lösen kann, liegt meist auf der Hand, da man dann ja den besten Wert kennt. Andersherum funktioniert es meist, indem man z.B. den Wert $k$ aus dem obigen Beispiel wie bei einer binären Suche immer weiter halbiert oder indem die Probleminstanz sukzessive geändert wird, hier z.B. indem einzelne Knoten entfernt werden und geprüft wird, ob ein Entscheidungsverfahren immer noch akzeptiert. Wir merken uns an dieser Stelle einfach, dass die Entscheidungs- und die Optimierungsvariante eines Problems so ähnlich sind, dass man, wenn man das eine schnell (also mit einem Polynomialzeitalgorithmus) lösen kann, auch das andere schnell (mit einem Polynomialzeitalgorithmus) lösen kann. Es genügt daher, sich auf die, für die Theorie angenehmeren, Entscheidungsvarianten zu konzentrieren und mit diesen eine für die Praxis relevante Theorie aufzubauen.

Hier ein paar Fragen zur Zeit- und Platzkomplexität.

Komplexitätstheorie

Posted On 8 Dez 2014
By fgi1
In Uncategorized

Download PDF

Bisher haben wir Probleme mit Turingmaschinen (bzw., was ja wegen der Church-Turing-These das gleiche ist, mit einem Algorithmus) gelöst. Dabei ging es bei der Entscheidbarkeit bzw. Unentscheidbarkeit eines Problems zunächst darum, ob ein Problem prinzipiell gelöst werden kann oder nicht. Für die Praxis reicht diese Unterscheidung aber in den allermeisten Fällen nicht. Wenn ein Problem zwar lösbar ist, die Zeit zur Lösung des Problems aber inakzeptabel ist, dann ist das Problem praktisch nicht lösbar. Hat man bspw. einen Algorithmus für ein Graphenproblem, der $2^n$ viele Schritte zur Lösung des Problems braucht, wobei $n$ die Anzahl der Knoten des Graphen ist. Dann ist dies für kleine Werte von $n$ wie $n = 20$ oder $n = 30$ vielleicht noch akzeptabel, für z.B. $n = 100$ wird die Berechnung einer Lösung aber nicht mehr möglich sein, weil diese schlicht zu lange dauert.

Entsprechend verhält es sich bei dem Erfüllbarkeitsproblem der Aussagenlogik, also bei dem Problem gegeben eine aussagenlogische Formel, ist diese erfüllbar oder nicht? Hat eine Formel $n$ verschiedene Aussagensymbole, so hat die Wahrheitstafel, aus der man die Lösung ablesen kann, $2^n$ viele Zeilen. Die Berechnung all dieser Zeilen dauert für größere $n$ schlicht zu lange.

In der Komplexitätstheorie geht es nun zunächst darum, formal ein Maß für die Zeitkomplexität und die Platzkomplexität einer Berechnung zu definieren. Im Anschluss wird es dann darum gehen, wie man untere Schranken für ein Problem definieren kann, d.h. wie man ausdrücken kann, dass ein Problem (wie z.B. das Erfüllbarkeitsproblem der Aussagenlogik) auf keinen Fall schneller als eine bestimmte untere Schranke gelöst werden kann. Wir werden sehen, dass eine solche Schranke nicht einfach zu bestimmen ist. Tatsächlich stellt dies die Informatiker vor sehr große Probleme und wir können bisher nur Aussagen treffen, dass es mit einer hohen Wahrscheinlichkeit wohl keine Möglichkeit gibt, ein Problem schnell zu lösen. Aber Techniken, um dies mit Sicherheit zeigen zu können, sind im Moment außerhalb unserer Möglichkeiten. Diese Überlegungen werden in das Themengebiet $P$, $NP$ und $NP$-Vollständigkeit münden.

Unentscheidbarkeit (und darüberhinaus)

Posted On 7 Dez 2014
By fgi1
In Uncategorized

Download PDF

Wir haben nun etliche entscheidbare Sprachen gesehen und mit $TM_{acc}$ eine Sprache gesehen, die wir zwar aufzählen können, für die es uns aber schwer fällt, eine Turingmaschine anzugeben, die sie entscheidet. Tatsächlich ist dies auch nicht möglich und dies wollen wir in diesem Abschnitt zeigen.

Darauf aufbauend wollen wir dann noch weitere Probleme als unentscheidbar nachweisen und auf diese Weise eine Technik kennenlernen, mit der wir Probleme als unentscheidbar nachweisen können.

Zum Abschluss wollen wir dann noch eine Sprache sehen, die nicht einmal mehr aufzählbar ist.

Ein unentscheidbares Problem

Wir wollen in diesem Abschnitt zeigen, dass die Sprache $$ TM_{acc} = \{ \langle M, w \rangle \mid \text{$M$ ist eine TM und akzeptiert $w$}\} $$ nicht entscheidbar ist. Wir wissen bereits, dass $TM_{acc}$ aufzählbar ist (man starte einfach $M$ auf $w$ und akzeptiere, wenn $M$ dies tut) und Versuche $TM_{acc}$ zu entscheiden schlagen fehl, aber ein Beweis, dass dies tatsächlich nicht möglich ist, steht noch aus. Dies werden wir gleich nachholen. Vorher wollen wir noch einmal betonen, wie bedeutend diese und verwandte Fragestellungen sind. Die Frage, ob eine Turingmaschine $M$ auf einem Eingabewort $w$ anhält, ist im Grunde die selbe wie die Frage, ob ein Programm in einer Programmiersprache wie Java oder C bei einer bestimmten Eingabe anhält. Diese Frage nicht algorithmisch lösen zu können ist ein ernstes Problem in der Verifikation von Software und Hardware und schränkt uns bedeutend ein. Zudem macht uns die Erkenntnis, dass es ein nicht entscheidbares Problem gibt, ganz deutlich, dass ein Computer nicht alles kann. Es gibt Probleme, die sind einer Lösung durch ihn nicht zugänglich.

Satz 4.4.1

Die folgende Sprache ist nicht entscheibar $$ TM_{acc} = \{ \langle M, w \rangle \mid \text{$M$ ist eine TM und akzeptiert $w$}\} $$

Beweise

Angenommen $TM_{acc}$ wäre entscheidbar. Sei $H$ eine Turingmaschine, die $TM_{acc}$ entscheidet. Wir wollen nun einen Widerspruch erzeugen. Dies gelingt uns, indem wir mit erlaubten Konstruktionsschritten eine Turingmaschine bauen, die $H$ als Unterroutine benutzt und letztendlich dann aber paradoxe Dinge tut, also Dinge, die nicht sein können. Wir haben dann einen Widerspruch und da alle Zwischen- und Konstruktionsschritte aber möglich sind, muss die ursprüngliche Annahme falsch sein und $H$ kann also nicht existieren.

Sei also $H$ eine Turingmaschine, die $TM_{acc}$ entscheidet. $H$ tut folgendes:

$H$ akzeptiert $\langle M,w \rangle$, wenn $M$ das Wort $w$ akzeptiert.
$H$ lehnt $\langle M, w \rangle$ ab, wenn $M$ das Wort $w$ nicht akzeptiert.

Kürzer notieren wir dies hier als

$H(\langle M,w \rangle) = 1$, wenn $M(w) = 1$
$H(\langle M,w \rangle) = 0$, wenn $M(w) \not= 1$

Wir konstruieren nun eine TM $D$, die $H$ als Subroutine benutzt. $D$ nimmt als Eingabe eine TM $M$ (die Eingabe ist also $\langle M \rangle$) und arbeitet wie folgt:

Starte $H$ mit Eingabe $\langle M, \langle M \rangle \rangle$.
Drehe das Ergebnis von $H$ um und gebe es aus.

$D$ tut also nichts anderes als $H$ mit einer speziellen Eingabe zu starten. Damit ist nun

$D(\langle M \rangle) = 1$, wenn $M$ die Eingabe $\langle M \rangle$ nicht akzeptiert
$D(\langle M \rangle) = 0$, wenn $M$ die Eingabe $\langle M \rangle$ akzeptiert

Insgesamt haben wir damit jetzt

$\begin{eqnarray*}
H(\langle M,w \rangle) & = & \left\{ \begin{array}{ll}
1, & wenn~M(w) = 1 \\
0, & wenn~M(w) \not= 1
\end{array} \right. \\
D(\langle M \rangle) & = & \left\{ \begin{array}{ll}
1, & wenn~M(\langle M \rangle) \not= 1 \\
0, & wenn~M(\langle M \rangle) = 1
\end{array} \right.
\end{eqnarray*}$

Was passiert nun, wenn man $D$ mit $\langle D \rangle$ ausführt? Wenn man $D$ also sich selbst als Eingabe vorlegt? $D$ ruft dann ja $H$ auf, um zu ermitteln ob $D$ auf $D$ anhält — dreht dann aber noch das Ergebnis um! Setzt man oben bei $D(\langle M \rangle) = \ldots$ überall wo $M$ steht ein $D$ ein, so erhält man nun $$ D(\langle D \rangle) = \left\{ \begin{array}{ll}
1, & \text{wenn $D(\langle D \rangle) \not= 1$} \\
0, & \text{wenn $D(\langle D \rangle) = 1$}
\end{array} \right.$$

Dies ist ein Widerspruch! $D(\langle D \rangle)$ kann ja unmöglich $1$ sein, wenn es nicht $1$ ist oder $0$ wenn es $1$ ist. Dies macht keinen Sinn und wir haben einen Widerspruch. Damit kann die Annahme nicht stimmen und $H$ kann nicht existieren. $TM_{acc}$ ist also unentscheidbar!

Mit diesem Ergebnis haben wir eine erste nicht entscheidbare Sprache gefunden. Da wir wissen, dass $TM_{acc}$ aufzählbar ist, haben wir damit nun $\text{REC} \subset \text{RE}$ und damit insgesamt $$ \text{REG} \subset \text{CF} \subset \text{REC} \subset \text{RE}. $$

Man mache sich einmal klar, wie obiger Beweis funktionieren würde, wenn man statt mit einer Turingmaschine $H$ mit einer Java-Routine argumentieren würde. Nehmen wir also an, es gäbe eine Java-Routine $f$, die eine andere Java-Routine $g$ und deren Argumente als Eingabe nimmt und true zurückliefert, wenn $g$ true liefert und false sonst. Die Argumentation liefe dann ganz genau so! Das obige Problem ist nicht eines, das auf Turingmaschinen beschränkt ist. Es gilt ganz genauso für gängige Programmiersprachen und zeigt uns damit sehr drastisch unsere Grenzen auf.

Weitere unentscheidbare Probleme

Wir wollen nun eine Technik vorstellen, mit der man Probleme als unentscheidbar nachweisen kann. Diese Technik ist im Kern ein Widerspruchsbeweis. Wir wollen die Technik dann im Anschluss an einem einfachen und einem komplizierteren Problem einüben.

Will man ein neues Problem, ausgedrückt durch eine Sprache $L$, als unentscheidbar nachweisen, so ist das übliche Vorgehen das folgende:

Wir nehmen an, $L$ wäre entscheidbar. Sei $M$ eine Turingmaschine, die $L$ entscheidet.
Unter Nutzung von $M$ ($M$ wird also quasi als Unterroutine benutzt) wird nun eine Turingmaschine konstruieren, die eine schon als unentscheidbar nachgewiesene Sprache entscheidet.
Das ist dann ein Widerspruch, also kann $M$ nicht existieren.

Man nennt dies eine \emph{Reduktion}, und sagt, dass das unentscheidbare Problem auf das neue Problem reduziert wurde (bzw. die Sprachen aufeinander reduziert wurden).

Um die Technik zu illustrieren, zeigen wir zunächst die Unentscheidbarkeit einer Sprache, die der Sprache $TM_{acc}$ sehr ähnelt. Bei $TM_{acc}$ ging es um die Akzeptanz eines Wortes. Nun geht es nur noch um das Halten der Turingmaschine.

Satz 4.4.2

Die Sprache $$ TM_{halt} := \{ \langle M, w \rangle \mid \text{$M$ ist eine TM und hält auf $w$}\} $$ ist nicht entscheidbar.

Beweise

Wie in dem Vorgehen oben beschrieben, nehmen wir zunächst an $TM_{halt}$ wäre entscheidbar. Sei $H$ eine Turingmaschine, die $TM_{halt}$ entscheidet. Unser Ziel ist es nun, eine neue Turingmaschine zu konstruieren, die $H$ als Unterroutine benutzt, und die eine Sprache entscheidet, von der wir schon wissen, dass sie unentscheidbar ist. Da wir bisher nur eine unentscheidbare Sprache kennen, ist das Ziel hier einfach zu formulieren: Wir wollen eine Turingmaschine konstruieren, die $TM_{acc}$ entscheidet.

Wir geben nun die Arbeitsweise einer neuen Turingmaschine $S$ an, die $TM_{acc}$ entscheiden soll. $S$ benutzt die Turingmaschine $H$, die nach Annahme $TM_{halt}$ entscheidet. Bei Eingabe $\langle M, w \rangle$ arbeitet $S$ wie folgt:

Starte $H$ mit Eingabe $\langle M, w \rangle$.
Lehnt $H$ ab, lehne ab.
Akzeptiert $H$, simuliere $M$ auf $w$.
Wenn $M$ akzeptiert, akzeptiere, sonst lehne ab.

Wie kommt man auf diese Turingmaschine?

Bevor wir gleich zeigen, dass $S$ tatsächlich $TM_{acc}$ entscheidet, wollen wir einmal darauf eingehen, wie man auf die Arbeitsweise von $S$ kommt. Unser Ziel ist es ja, $TM_{acc}$ zu entscheiden. Unsere Eingabe ist also die Kodierung einer Turingmaschine $M$ und eines Wortes $w$ und wir wollen entscheiden, ob $M$ das Wort $w$ akzeptiert. Würden wir nun einfach $M$ auf $w$ starten bzw. simulieren, so hätten wir Probleme, wenn diese Simulation nicht abbricht. Dies ist tatsächlich das einzige Problem, denn es gibt ja nur drei Fälle: Entweder erreicht $M$ auf $w$ einen Endzustand. Dann kann die Simulation aufhören, da wir nun wissen, dass $M$ das Wort $w$ akzeptiert. Dann kann es sein, dass $M$ anhält und im Laufe der Rechnung nie einen Endzustand besucht hat. Auch dann können wir mit Sicherheit die Eingabe ablehnen, da $M$ also $w$ nicht akzeptiert. Und zuletzt gibt es noch den Fall, dass $M$ immer weiter läuft und zwar nie einen Endzustand besucht aber auch nie aufhört zu rechnen, die Simulation stoppt also nie. Diesen dritten, störenden Fall, können wir nun aber gerade durch eine Turingmaschine, die $H$ entscheidet, abfangen. Wir fragen $H$, ob $M$ auf $w$ anhält. Ist dies nicht der Fall, können wir (ohne $M$ zu simulieren!) sofort ablehnen, da wir dann wissen, dass $M$ immer weiter rechnet und nicht akzeptieren kann. -- Moment! An dieser Stelle tritt nun noch ein störender Fall auf. Nach unserer Definition kann eine Turingmaschine immer weiter rechnen und trotzdem (vorher mal) einen Endzustand besucht haben, also das Wort akzeptieren. Es gibt also auch unendlich lange Erfolgsrechnungen! Um mit diesem Problem fertig zu werden, geht man entweder davon aus, dass die Turingmaschine sofort als Eingabe so gegeben ist, dass aus einem Endzustand keine Kanten mehr herausführen (eine Rechnung in einem Endzustand also stets endet) oder aber man (und dies rechtfertigt auch, dass man das zuvor gesagte überhaupt annehmen darf) lässt obige Turingmaschine $S$ als erste noch den Schritt machen, dass sie $M$ gerade so anpasst, das sie alle Kanten, die bei $M$ aus Endzuständen herausführen, entfernt.

Nun klappt die Überlegung von eben. Wir fragen also $H$, ob $M$ auf $w$ anhält. Tut $M$ dies nicht, dann wissen wir, dass $M$ nicht akzeptiert. Sagt uns $H$ aber, dass $M$ auf $w$ anhält, dann können wir nun sorglos, $M$ auf $w$ simulieren, denn die Simulation muss nach endlich vielen Schritten anhalten (gerade dies hat uns $H$ ja eben gesagt). Die Simulation endet dann entweder in einem Endzustand oder nicht und wir wissen dann, ob $M$ das Wort $w$ akzeptiert oder nicht und können entsprechend antworten.

So kann man auf die Idee kommen, wie $S$ zu konstruieren ist. Die Fragen, die man sich bei der Konstruktion stellen muss sind, welche Probleme treten auf, wenn ich die Sprache $TM_{acc}$ entscheiden will und wie kann mir eine Turingmaschine, die $TM_{halt}$ entscheidet, dabei helfen?

Wir zeigen nun noch, dass $S$ tatsächlich die Sprache $TM_{acc}$ entscheidet. Zunächst merken wir noch an, dass $S$ als erstes, was wir oben nicht extra erwähnt haben, die Eingabe auf syntaktische Korrektheit prüft und dass $S$ alle Kanten, die bei $M$ aus Endzuständen herausführen, entfernt. Eine Erfolgsrechnung von $M$ hält damit in einem Endzustand, sobald ein Endzustand das erste Mal besucht wird. Beides wird oft nicht mehr explizit erwähnt.

Wir wollen nun zeigen, dass $S$ die Sprache $TM_{acc}$ entscheidet. Dazu müssen wir zeigen, dass $S$ stets anhält und dass tatsächlich $L(S) = TM_{acc}$ gilt. Zunächst terminieren die ersten beiden Schritte nach endlich viel Zeit, da $H$ die Sprache $TM_{halt}$ entscheidet und daher auch stets terminiert. Nun starten wir im dritten Schritt $M$ nur dann auf $w$, wenn vorher $H$ akzeptiert hat. Dies bedeutet aber ja gerade, dass $M$ auf $w$ anhält. Daher endet die Simulation im dritten Schritt auch nach endlich vielen Schritten. Der vierte Schritt terminiert auch und damit terminiert $S$ stets und hält an.

Nun zu der Korrektheit der Antwort. Diese ist schnell zu sehen. Wenn $S$ bereits im zweiten Schritt ablehnt, dann tut sie dies, wenn $H$ ablehnt, was bedeutet, dass $M$ auf $w$ nicht anhält. Mit der Manipulation von eben kann also kein Endzustand besucht werden (da $M$ sonst ja anhalten würde) und also akzeptiert $M$ ganz bestimmt nicht $w$. Daher ist diese Antwort richtig. Sonst wird im dritten Schritt $M$ auf $w$ simuliert und ja gerade akzeptiert, wenn $M$ akzeptiert und abgelehnt, wenn $M$ dies tut. Damit akzeptiert $S$ genau dann, wenn $M$ das Wort $w$ akzeptiert und wir sind fertig.

Da wird nun eine Turingmaschine haben, die eine unentscheidbare Sprache entscheidet, ist dies ein Widerspruch und die ursprüngliche Annahme muss falsch sein. $TM_{halt}$ ist also unentscheidbar.

$TM_{halt}$ wird als Halteproblem bezeichnet und tritt oft in der Literatur auf. Die Sprachen $TM_{halt}$ und $TM_{acc}$ sind allerdings so ähnlich, dass einige Autoren auch $TM_{acc}$ als Halteproblem bezeichnen.

Der Beweis, dass $TM_{halt}$ unentscheidbar ist, verlief noch recht übersichtlich. Als zweites Beispiel für einen Unentscheidbarkeitsbeweis wollen wir ein komplizierteres Problem betrachten. Wir nennen dafür einen Zustand einer Turingmaschine einen \emph{nutzlosen Zustand}, wenn er bei keinem Eingabewort jemals besucht wird.

Satz 4.4.3

Die Sprache $$ \texttt{UselessState} = \{\langle A,q \rangle \mid A \text{ ist eine TM und $q$ ein nutzloser Zustand von $A$}\} $$ ist unentscheidbar.

Beweise

Wir nehmen zunächst wieder an, $\texttt{UselessState}$ wäre entscheidbar. Sei $A_{US}$ eine Turingmaschine, die das Problem entscheidet. Wir wollen damit nun das Halteproblem $TM_{halt}$ entscheiden.

Wir beachten zunächst, dass die folgende Konstruktion möglich ist: Zu einer gegebenen Turingmaschine $M$ mit Zustandsmenge $Z$ und Bandalphabet $\Gamma$ kann eine Turingmaschine $M‘$ konstruiert werden mit

einem neuen Zustand $z_{neu}$ und
für jeden Zustand $z \in Z$ von $M$ und jedes Symbol $x \in \Gamma$, für das es keinen Übergang aus $z$ in $M$ gab (d.h. es gab keine Kante $(z,x,X,Y,z‘)$ in $M$ mit $X, Y, z‘$ beliebig) wird eine neue Kante $(z,x,x,R,z_{neu})$ hinzugefügt

Mit dieser Konstruktion erreicht man folgendes: hält $M$ an, so kann $M‘$ noch einen Übergang nach $z_{neu}$ machen. Dort hält dann $M‘$. $M$ hält also genau dann in irgendeinem Zustand, wenn $M‘$ in $z_{neu}$ hält. Man beachte, wie hier ein Zusammenhang zwischen dem Halten von $M$ und dem Benutzen des Zustandes von $M‘$ hergestellt wird. Ein Problem ist nun noch, dass $z_{neu}$ nur dann nutzlos wäre, wenn $M$ auf keinem Eingabewort anhält. Für das Halteproblem ist aber nur gefragt, ob $M$ auf $w$ anhält. Nun ist es aber zu $M$ und $w$ möglich eine Turingmaschine $M“$ zu konstruieren, die bei jeder Eingabe das Band löscht und dann $w$ auf $M‘$ startet, wobei $M‘$ wie eben beschreiben aus $M$ hervorgeht. Damit tut $M“$ dann bei jeder Eingabe das gleiche (nämlich im Grunde $M$ auf $w$ zu starten). Wenn nun aber $M$ auf $w$ hält, dann hält $M“$ in $z_{neu}$ (und besucht daher insbesondere $z_{neu}$). Wenn $M$ auf $w$ nicht hält, dann besucht $M“$ den Zustand $z_{neu}$ nicht und tut dies bei keinem Eingabewort (da ja bei jedem $M$ auf $w$ gestartet wird), d.h. $z_{neu}$ wäre dann nutzlos.

Mit diesen Überlegungen können wir nun die Arbeitsweise einer Turingmaschine $S$ angeben, die $\texttt{UselessState}$ entscheidet. Bei Eingabe $\langle M, w \rangle$ arbeitet $S$ wie folgt:

Konstruiere aus $\langle M,w \rangle$ die oben beschriebene Turingmaschine $M“$.
Starte $A_{US}$ auf $\langle M“,z_{neu} \rangle$.
Akzeptiert $A_{US}$, dann ist $z_{neu}$ ein nutzloser Zustand und nach obigem hält dann $M$ nicht auf $w$ und wir lehnen ab.
Lehnt $A_{US}$ ab, so ist $z_{neu}$ nicht nutzlos, wird also besucht. Dann aber hält $M$ auf $w$ an und wir akzeptieren.

Man kann wieder schnell argumentieren, dass $S$ stets terminiert. Insbesondere terminieren die ersten beiden Schritte und daher auch $S$. Mit obigen Erklärungen ist auch klar, dass $S$ gerade in den richtigen Fällen die Eingabe akzeptiert. Damit entscheidet $S$ das Halteproblem, was aber nicht sein kann. $A_{US}$ existiert also nicht und $\texttt{UselessState}$ ist folglich unentscheidbar.

Ein kompakterer Beweis

Will man nicht ganz so ausführlich vorgehen und wie oben neue Kanten explizit beschreiben, so genügt es auch wie folgt ähnlich aber mit einer kleinen Variation vorzugehen und insb. einen etwas höheren Abstraktionsgrad beim Beweis zu wählen.

Wir nehmen wieder an das Problem sei entscheidbar und $A$ eine Turingmaschine, die es entscheidet. Man kann nun bei Vorlage von $M$ und $w$ (für das Halteproblem) eine Turingmaschine $M''$ konstruieren, die ihre Eingabe ignoriert und die stets $M$ auf $w$ simuliert. $M''$ wechselt, sollte $M$ anhalten, dann noch in einen neuen Zustand $z_{neu}$, der sonst nicht besucht wird. (Wichtig hierfür ist sich klar zu machen, dass $M''$ tatsächlich $M$ simulieren kann und prüfen kann, ob $M$ anhält.) Eine Turingmaschine, die das Halteproblem entscheidet, arbeitet nun wie folgt: Bei Vorlage von $M$ und $w$, wird $M''$ konstruiert und $A$ wird $M''$ und $z_{neu}$ vorgelegt. Akzeptiert $A$, so ist $z_{neu}$ nutzlos, was bedeutet, dass $M$ auf $w$ nicht anhält und wir lehnen ab. Lehnt $A$ ab, so ist $z_{neu}$ nicht nutzlos, also hält $M$ auf $w$ und wir akzeptieren. Die Turingmaschine entscheidet damit das Halteproblem, was nicht sein kann.

Hier haben wir also durch die auf einem höheren Abstraktionsgrad beschriebene Konstruktion erheblich den Beweis abgekürzt. Dafür wird aber mehr vom Leser verlangt.

Damit haben wir von zwei weiteren Problemen gezeigt, dass sie unentscheidbar sind. Will man von einem neuen Problem zeigen, dass es unentscheidbar ist, so wendet man die eingangs vorgestellte Technik der Reduktion an. Es ist dabei aber ein kreativer Vorgang, die Turingmaschine zu konstruieren, die das Problem entscheidet, von dem man schon wei{\ss}, dass es unentscheidbar ist. Das zweite Beispiel illustriert recht gut, dass dies recht schnell zu einer Herausforderung werden kann. Mit etwas Übung kann man aber lernen, unentscheidbare Probleme in vielen Fällen recht gut erkennen zu können.

Nicht mal mehr aufzählbar

Nachdem wir nun mehrere unentscheidbare Probleme kennengelernt haben und in der Kette der Sprachfamilien $$ \text{REG} \subset \text{CF} \subset \text{REC} \subset \text{RE}. $$ für jede Sprachfamilie Sprachen kennen, die in dieser Klasse liegen, aber nicht mehr in den darunter liegenden Klassen, kann man sich nun noch die Frage stellen, ob es nicht sogar Sprachen gibt, die nicht einmal mehr in RE sind? Solche Sprachen gibt es tatsächlich. Für eine solche Sprache gibt es also nicht einmal mehr eine Turingmaschine, die sie akzeptiert.

Um diese Sprache ausdrücken zu können, überlegen wir uns zunächst folgendes. Wir halten ein Alphabet wie z.B. $\{0,1\}$ fest. Die Worte, die mit diesem Alphabet gebildet werden können, können wir erst der Länge nach sortieren. Worte gleicher Länge sortieren wir dann noch lexikalisch, wobei $0$ in der Ordnung vor $1$ kommt. Die Worte lassen sich dann auflisten $$ 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, 0000, \ldots $$ So kann man dann von einem Wort $w_1, w_2, w_3, \ldots$ sprechen.

Ganz genauso können wir eine Turingmaschine $M$ über dem Alphabet $\{0,1\}$ kodieren, z.B. indem wir zunächst jedes Element des Tupels $M = (Z, \Sigma, \Gamma, \delta, z_0, Z_{end})$ mit unserem normalen Alphabet aufschreiben und die so entstandene Zeichenkette dann binär kodieren (ein Computer tut ja auch nichts anderes, wenn er eine Zeichenkette speichert). Wir können dann die Zeichenketten, die tatsächlich eine Turingmaschine kodieren so wie eben zunächst nach Länge und dann lexikalisch sortieren. Dies ergibt dann wieder eine Auflistung $M_1, M_2, M_3, \ldots$ aller Turingmaschinen.

Insgesamt haben wir jetzt also über dem Alphabet $\{0,1\}$ eine Auflistung aller Worte $w_1, w_2, w_3, \ldots$ und eine Auflistung aller Turingmaschinen $M_1, M_2, M_3, \ldots$. Man beachte, dass dies alle Turingmaschinen sind, nicht bloss z.B. alle Turingmaschinen auf dem Eingabealphabet $\{0,1\}$. Die Turingmaschinen werden lediglich mit dem Alphabet $\{0,1\}$ kodiert, es werden aber alle möglichen Turingmaschinen aufgelistet.

Wir können nun die Sprache $L_d$ definieren und zeigen, dass diese nicht aufzählbar ist. Der Index $d$ steht dabei für diagonal. Warum wird im Beweis deutlich.

Satz 4.4.4

Die Sprache $$ L_d := \{ w_i \mid w_i \not\in L(M_i) \} $$ ist nicht aufzählbar.

Beweise

Man kann die Wörter und die Turingmaschinen in einer Matrix anordnen:
$$ \begin{array}{cccccc||c}
& M_1 & M_2 & M_3 & M_4 & \ldots & L_d\\
w_1 & 1 & 1 & 0 & 0 & & Nein (w_1 \not\in L_d)\\
w_2 & 1 & 0 & 0 & 0 & \ldots & Ja (w_2 \in L_d)\\
w_3 & 0 & 1 & 1 & 1 & \ldots & Nein (w_3 \not\in L_d)\\
w_4 & 0 & 0 & 1 & 0 & & Ja (w_4 \in L_d)\\
. & . & . & . & . & . & .
\end{array} $$

Eine $1$ bei z.B. $w_2$ und $M_1$ bedeutet, dass die Turingmaschine $M_1$ das Wort $w_2$ akzeptiert, während eine $0$ bei z.B. $w_2$ und $M_2$ bedeutet, dass $M_2$ das Wort $w_2$ nicht akzeptiert. Es ist nicht wichtig, ob die Turingmaschinen $M_1$ und $M_2$ anhalten oder ähnliches. Wichtig ist nur, dass $M_1$ und $M_2$ Turingmaschinen sind und als solche eine Sprache akzeptiert. Ein Wort ist also entweder in dieser Sprache enthalten oder nicht. Dies wird durch die Matrix ausgedrückt. Es wird nicht behauptet, dass dies gerade berechnet wird oder ähnliches.

Die Sprache $L_d$ wird nun gerade aus der Diagonalen in obiger Matrix gewonnen, wobei nur die Einträge mit $0$ in $L_d$ aufgenommen werden, d.h. ein Wort $w_i$ ist genau dann in $L_d$ enthalten, wenn $M_i$ das Wort $w_i$ nicht akzeptiert.

Die Kernidee des Beweises ist nun, dass eine Turingmaschine, die $L_d$ akzeptiert, ein $M_j$ in der Matrix sein müsste. Dies wird dann aber zu einem Widerspruch mit dem Wort $w_j$ führen, dass gleichzeitig enthalten und nicht enthalten sein müsste.

Wir führen dies genauer aus. Angenommen $L_d$ wäre aufzählbar, dann gibt es eine Turingmaschine $M_j$ aus der Auflistung mit $L(M_j) = L_d$, denn in der Auflistung sind ja alle Turingmaschinen enthalten. Betrachten wir nun das Wort $w_j$. Es muss entweder $w_j \in L_d$ oder $w_j \not\in L_d$ sein. Beide Fälle führen aber zu einem Widerspruch:

Ist $w_j \in L_d$, dann ist nach der Definition von $L_d$ also $w_j \not\in L(M_j)$. Da aber $L(M_j) = L_d$ hei{\ss}t dies, dass $w_j \not\in L_d$ sein müsste. Ein Widerspruch zu $w_j \in L_d$, wovon wir ausgegangen waren.
Ist $w_j \not\in L_d$, dann ist wegen $L(M_j) = L_d$ also $w_j \not\in L(M_j)$. Nach der Definition von $L_d$ ist dann aber $w_j \in L_d$ und wir haben wieder einen Widerspruch, denn wir waren ja von $w_j \not\in L_d$ ausgegangen.

Daher kann es keine Turingmaschine geben mit $L(M_j) = L_d$ und damit ist $L_d$ nicht aufzählbar.

Damit haben wir eine Sprache kennengelernt, die nicht einmal mehr aufzählbar ist. Zumindest ist $L_d$ aber abzählbar. Nicht einmal mehr abzählbar sind dann z.B. die reellen Zahlen.

Wiederholung

Wir haben in diesem Abschnitt gesehen, dass es unentscheidbare Probleme gibt und mehrere kennengelernt. Ferner haben wir noch eine Sprache gesehen, die nicht einmal mehr aufzählbar ist. Unser Wissen bezüglich unserer vier bisher eingeführten Sprachfamilien REG, CF, REC und RE stellt sich nun so dar $$ \text{REG} \subset \text{CF} \subset \text{REC} \subset \text{RE} $$

Eine typische Sprache in REG ist z.B. die durch den regulären Ausdruck $a^*$ beschriebene. Eine typische Sprache in CF, die nicht mehr in REG ist, ist z.B. $\{a^n b^n \mid n \in \mathbb{N}\}$. Eine entscheidbare Sprache, die nicht mehr kontextfrei ist, ist z.B. $\{a^n b^n c^n \mid n \in \mathbb{N}\}$ und eine typische unentscheidbare, aber aufzählbare Sprache ist durch das Halteproblem gegeben. Nicht einmal mehr aufzählbar ist dann die Sprache $L_d$.

Die entscheidbaren Sprachen sind aus der Sicht der Informatik besonders interessant, da sie einer Lösung durch einen Algorithmus zugänglich sind. Bei den entscheidbaren Sprachen geht es allerdings zunächst nur darum, dass sie überhaupt lösbar sind. Für die Praxis genügt dies oft nicht. Hier sind noch die benötigten Ressourcen zur Lösung des Problems von Bedeutung. Insbesondere fragt man, wie viel Zeit und wie viel Speicher zur Lösung eines Problemes benötigt wird. Es kann passieren, dass ein Problem zwar lösbar ist, dass aber zuviel Zeit benötigt wird und dies daher aus praktischer Sicht nicht umsetzbar ist. Diese Fragen führen in den Bereich der Komplexitätstheorie, die versucht Aussagen über den benötigten Zeit- und Platzbedarf bei der Lösung eines Problems zu machen und einen Begriff von "praktisch nicht lösbar" zu etablieren. Wir kommen darauf im späteren Verlauf noch zu sprechen.

Hier ein paar Fragen zur Unentscheidbarkeit.

Entscheidbarkeit und Aufzählbarkeit

Posted On 6 Dez 2014
By fgi1
In Uncategorized

Download PDF

Nachdem wir nun die Turingmaschine und verschiedene Varianten kennengelernt haben, wollen wir nun, so wie wir es auch bei den regulären und den kontextfreien Sprachen gemacht haben, eine zugehörige Sprachfamilie definieren. Dies machen wir zunächst ganz genauso wie bei endlichen Automaten und betrachten die Familie all jener Sprachen, die von Turingmaschinen akzeptiert werden. Dann werden wir aber sogar noch eine zweite Sprachfamilie einführen, bei der es um Sprachen geht, die nicht nur von Turingmaschinen akzeptiert werden, sondern für die sogar Turingmaschinen existieren, die stets anhalten. Diese Sprachfamilie ist für die Informatik von besonderer Bedeutung, denn da wir Turingmaschinen als abstraktes Modell für das Berechenbare bzw.~für einen Algorithmus kennengelernt haben und da wir gesehen haben, dass das Akzeptieren von Sprachen und das Berechnen von Funktionen im Grunde gleich sind, erfasst diese Sprachfamilie gerade jene Probleme, die von Algorithmen, die stets terminieren, lösbar sind und dies sind gerade jene Algorithmen, die man typischerweise versucht zu entwerfen.

Im Anschluss werden wir dann ganz so wie schon bei REG und CF sehen, dass es Probleme gibt, die nicht mehr in diesen neuen Sprachfamilien liegen. Dies ist aber deshalb von deutlich schwerwiegenderer Bedeutung, da dies dann bedeutet, dass es keine Turingmaschine für ein Problem gibt, was bedeutet, dass es auch keinen Algorithmus ausgeführt auf irgendeinem Computer gibt, der das Problem löst. Da wir sehen werden, dass dies auch Probleme betrifft, die von großer praktischer Bedeutung sind, lernen wir damit eine wichtige Grenze unserer Möglichkeiten mit dem Computer kennen.

Die Sprachfamilien RE und REC

Als erstes können wir so wie wir es auch bei z.B. endlichen Automaten gemacht haben, einfach alle Sprachen, die von Turingmaschinen akzeptiert werden, in einer Sprachfamilie sammeln. Dies ergibt die Sprachfamilie der aufzählbaren Sprachen. Sie wird mit RE abgekürzt.

Definiton 4.3.1 (Die aufzählbaren Sprachen)

Eine Menge $M \subseteq \Sigma^*$ ist (rekursiv) aufzählbar genau dann, wenn eine DTM $A$ existiert mit $L(A) = M$.
Die Familie aller aufzählbaren Mengen bzw. Sprachen wird mit RE (recursively enumerable) bezeichnet.

Da die Turingmaschine anders als die bisherigen Automatenmodelle einen Unterschied macht zwischen Akzeptanz und dem tatsächlichen Halten (ein Wort muss ja nicht bis zum Ende gelesen werden, um es zu akzeptieren) und da das Halten aus algorithmischer Sicht von großer Bedeutung ist, da dies gleichbedeutend damit ist, dass ein Algorithmus bei jeder Eingabe terminiert, lohnt es sich, die Sprachen, die von Turingmaschinen akzeptiert werden können, die bei jeder Eingabe halten, in einer gesonderten Familie zu sammeln.

Definiton 4.3.2 (Die entscheidbaren Sprachen)

Eine Menge $M \subseteq \Sigma^*$ ist genau dann, wenn eine DTM $A$ existiert mit $L(A) = M$ und derart, dass $A$ auf jeder Eingabe anhält.
Die Familie aller entscheidbaren Mengen wird mit REC (recursive sets) bezeichnet.

Die von Turingmaschinen akzeptierten Sprachen bilden also die Sprachfamilie RE der aufzählbaren Sprachen. Die von Turingmaschinen, die stets anhalten, akzeptierten Sprachen bilden die Sprachfamilie REC der entscheidbaren Sprachen.

Hinweis zu REC und RE

Ist eine Sprache $M$ also entscheidbar, dann gibt es eine Turingmaschine $A$ mit $L(A) = M$ und ferner hält $A$ auf jeder Eingabe (in einem Endzustand, wenn das vorgelegte Wort in $M$ ist, sonst in einem Nicht-Endzustand).

Ist eine Sprache $M$ aufzählbar, dann gibt es (nur) eine Turingmaschine $A$ mit $L(A) = M$.

Bei einer aufzählbaren Menge muss die Turingmaschine also insb. nicht bei jeder Eingabe anhalten. Bei Worten die in $M$ sind, tut sie es (zumindest ist es leicht möglich $A$ so zu konstruieren, indem man alle Kanten, die aus Endzuständen rausführen, entfernt). Bei Worten, die nicht in $M$ sind, tut sie es aber nicht zwingend. Rechnet $A$ dann lange, dann kann dies also daran liegen, dass das Wort zwar in $M$ ist, $A$ aber noch einige Zeit braucht, um dies zu berechnen, oder daran, dass das Wort nicht in $M$ ist. Wir werden später noch sehen, dass es aufzählbare Sprachen gibt, die nicht entscheidbar sind. Für diese Sprachen ist dann genau das Problem, dass man den oben beschriebenen Fall nicht auflösen kann, d.h. man weiß dann nicht (und hat auch keine Möglichkeit dies herauszufinden), ob $A$ nur noch länger rechnen muss, um zu einem Ergebnis zu kommen, oder ob $A$ nie zu einem Ergebnis kommt.

Bisher haben wir noch kein Problem, das in RE ist, nicht aber in REC. Aus der Definition folgt aber zumindest sofort $\text{REC} \subseteq \text{RE}$, denn eine Turingmaschine, die ein Problem entscheidet, die zählt dieses auch auf (dass sie zusätzlich sogar immer hält, wird sozusagen gar nicht benötigt).

Exkurs: Äquivalente Definitionen von REC und RE

Es gibt einige äquivalente Definitionen der Sprachfamilien REC und RE. Einige sind in den folgende beiden Sätze zusammengefasst. Die charakteristische Funktion $\chi_M$ einer Menge $M$ ist dabei definiert durch $\chi_M(x) = 1 \text{ gdw. } x \in M$.

Satz 4.3.3

Eine Menge $M \subseteq \Sigma^*$ heißt \textbf{entscheidbar} genau dann, wenn

die charakteristische Funktion $\chi_M : \Sigma^* \rightarrow \{0,1\}$ berechenbar ist,
eine DTM $A$ mit $L(A) = M$ existiert, die auf jeder Eingabe anhält.

Satz 4.3.4

Eine Menge $M \subseteq \Sigma^*$ heißt (rekursiv) aufzählbar genau dann, wenn

$M = \emptyset$ ist oder eine totale, berechenbare Funktion $g : \mathbb{N} \rightarrow \Sigma^*$ existiert mit $g(\mathbb{N}) = M$,
eine $k$-Band off-line TM existiert, die jedes Wort der Menge $M$ genau einmal auf ihr Ausgabeband schreibt,
$M = L(A)$ für eine DTM $A$ gilt.

Es ist eine gute Übung zu zeigen, dass die einzelnen Möglichkeiten tatsächlich äquivalent sind. Im ersten Fall zeigt man dafür, dass 1. und 2. sich gegenseitig implizieren und im zweiten Fall zeigt man, dass 2. aus 1. folgt, 3. aus 2. und zuletzt 1. aus 3. Dann hat man einen Ringschluss und ist fertig.

Beispiele entscheidbarer Sprachen

Wir wollen einige Beispiele für entscheidbare Sprache betrachten. Daraus wird dann auch als Zusammenhang zwischen allen bisher betrachteten Sprachfamilien $$ \text{REG} \subset \text{CF} \subset \text{REC} \subseteq \text{RE} $$ folgen.

Als Notation werden nachfolgend in den Sprachbeschreibungen eckige Klammern benutzt, um eine Kodierung zu notieren. Wir benutzen also z.B. $\langle A, w \rangle$, um eine Kodierung von $A$ und $w$ zu bezeichnen (z.B. ist dann $A$ ein Automat und $w$ ein Wort). Wir notieren allgemein $\langle M \rangle$ für ein mathematisches Objekt $M$ (DFA, PDA, TM, Wort, $\ldots$). Wichtig ist, dass man $M$ endlich beschreiben kann. Hat man z.B. einen DFA $A$, so könnte $\langle A \rangle$ einfach die Zeichenkette sein, die man erhält, wenn man alle Elemente von $A$ (Zustandsmenge, Eingabealphabet, Übergangsfunktion usw.) hintereinander schreibt. Wir wollen nicht genau auf die Kodierungen eingehen, aber es sollte klar sein, dass es eine gibt. Auch wenn wir als Menschen den DFA aufschreiben, benutzen wir ja eine Kodierung. Notieren wir diese als Zeichenkette im Computer, ergibt sich wieder eine Kodierung. Wichtig für uns ist, dass solche Kodierungen existieren und dass die Turingmaschine mit diesen arbeiten kann. So kann sie z.B. aus der Kodierung eines DFAs die Überführungsfunktion auslesen und damit arbeiten.

Satz 4.3.5

Die Sprache $$ DFA_{acc} := \{ \langle A, w \rangle \mid \text{$A$ ist ein DFA und akzeptiert $w$}\} $$ ist entscheidbar.

Beweise

Eine TM $M$, die $DFA_{acc}$ entscheidet, arbeitet wie folgt:

Simuliere $A$ mit Eingabe $w$
Endet die Simulation in einem Endzustand von $A$, akzeptiere, sonst lehne ab.

Für diese TM muss nun noch argumentiert werden, dass sie stets hält und dass sie stets die korrekte Antwort liefert. Wir wollen vorher aber noch einige Details liefern, die wir später dann meist nicht so ausführlich wiedergeben werden.

Zunächst soll die Eingabe $\langle A, w \rangle$ als „sinnvolle Repräsentation“ gegeben sein, z.B. als Liste der Komponenten von $A$ und diese Komponenten wieder als Listen der Elemente (alle Zustände hintereinander, dann die Symbole, dann die Übergangsfunktion als Liste von Tupeln usw.). Die DTM überprüft dann zu Anfang, ob wirklich ein DFA und ein Eingabewort vorliegt. Diese syntaktische Überprüfung geht stets problemlos, auch wenn die tatsächliche Implementierung in einer TM recht umständlich wird.

Bei der Simulation von $A$ merkt $M$ sich dann die aktuelle Position in $w$ und den aktuellen Zustand von $A$, also im Grunde die Konfiguration von $A$.

Dann wird immer für jedes Tupel aus Zustand $z$ (in dem $A$ sich gerade befindet) und Symbol $a$ (das $A$ gerade lesen soll) der Zustand entsprechend $\delta(z,a)$ gewechselt und die Position im Wort um eins erhöht (d.h. die Nachfolgekonfiguration wird bestimmt).

Liest $A$ das Wort zu Ende und ist dann in einem Endzustand, so akzeptiert $M$, sonst ([/latex]A[/latex] blockiert oder ist nicht in einem Endzustand) lehnt $M$ ab.

So konstruiert, hält die TM $M$ auf jeder Eingabe, denn wenn die Eingabe syntaktischer Unsinn ist, merkt sie dies sofort, ansonsten wird $A$ auf $w$ simuliert, was wegen der Eigenschaften des DFAs auch stets nach endlichen vielen Schritten zu einem Ergebnis führt (entweder hat $A$ das Wort $w$ zu Ende gelesen und ist in einem Endzustand oder $A$ hat das Wort $w$ zu Ende gelesen und ist nicht in einem Endzustand oder $A$ hat das Wort nicht zu Ende gelesen, hat aber für das gerade zu lesende Symbol in dem aktuellen Zustand keinen Übergang). Ferner gibt $M$ auch die korrekte Antwort aus, denn es ist leicht zu überprüfen, ob am Ende der Simulation $A$ in einem Endzustand ist oder nicht und ob das Wort zu Ende gelesen wurde oder nicht. Damit hält $M$ immer und gibt immer die korrekte Antwort aus, also entscheidet $M$ die Sprache $DFA_{acc}$.

Hinweis zu dem letzten Beweis

In der Literatur werden einige Schritte oft übersprungen. Z.B. wird auf die Syntaxprüfung meist nicht explizit eingegangen. Die Eingabe wird als syntaktisch korrekt vorausgesetzt. Dies liegt daran, dass stets gute Kodierungen möglich sind und daran, dass die Turingmaschine dann ggf. die Eingabe schnell auf syntaktische Korrektheit testen kann. Wir werden hierauf in der Zukunft auch meist verzichten.

Ferner wird die Arbeitsweise einer Turingmaschine stets auf einem gewissen Abstraktionslevel beschrieben. Welcher geeignet ist, hängt wieder von den Kenntnissen der Zielgruppe ab. So kann z.B. der Schritt "die Turingmaschine bestimmt den Nachfolgezustand des DFA" völlig in Ordnung sein, wenn jeder Leser gewisse Kenntnisse über DFAs hat und sich ggf. schnell selbst überlegen kann, dass dies klappt. Ein Schritt wie ``die Turingmaschine bestimmt alle Zustände des DFAs, die durch ein Wort aus $a^*$ erreichbar sind'' würde aber vermutlich eine ausführlichere Begründung, wie sie dies tut, erfordern.

Zur Übung ist es wieder zu Anfang gut, sich sehr kleinschrittig zu überlegen, was die Turingmaschine machen muss und dies auch aufzuschreiben. Beim Lesen anderer Beweise ist es zur Übung gut, sich zu überlegen, wie dargestellte abstraktere Schritte durch kleinere Schritte tatsächlich ausgeführt werden können.

Wir betrachten als weiteres Beispiel die ganz ähnliche Frage der Akzeptanz eines Wortes durch einen NFA.

Satz 4.3.6

Die Sprache $$ NFA_{acc} := \{ \langle A, w \rangle \mid \text{$A$ ist ein NFA und akzeptiert $w$}\} $$ ist entscheidbar.

Beweise

Man kann hier so ähnlich vorgehen wie oben, muss sich dann aber nach jedem gelesenen Buchstaben die Menge aller Zustände, in denen der NFA nichtdeterministisch ist, merken und diese Menge manipulieren. Dies gelingt dann auch, da man wieder zeigen kann, dass die Turingmaschine stets anhalten muss und auch die richtigen Antworten liefert. Alternativ kann man auf von uns bereits gezeigte Konstruktionen zurückgreifen. Eine Turingmaschine, die obiges Problem löst, kann bei Vorlage von $A$ und $w$ wie folgt arbeiten:

Konstruiere zu $A$ den Potenzautomaten $B$.
$B$ ist ein DFA. Benutze die im vorherigen Satz konstruierte TM $M$, um $\langle B, w \rangle \in DFA_{acc}$ zu entscheiden.
Akzeptiere, falls $M$ akzeptiert, sonst lehne ab.

Dieses Vorgehen klappt insb. deswegen, da wir von der Potenzautomatenkonstruktion wissen, dass sie korrekt ist und dass sie in einen stets terminierenden Algorithmus umgewandelt werden kann, der auch auf einer TM implementiert werden kann.

Die nächsten zwei Probleme hängen abermals mit endlichen Automaten zusammen.

Satz 4.3.7

Die Sprache $$ DFA_{\emptyset} := \{ \langle A \rangle \mid \text{$A$ ist ein DFA und $L(A) = \emptyset$}\} $$ ist entscheidbar.

Beweise

Die Entscheidbarkeit dieser Sprache behandeln wir in den Präsenzaufgaben.

Satz 4.3.8

Die Sprache $$ DFA_{=} := \{ \langle A, B \rangle \mid \text{$A$ und $B$ sind DFAs mit $L(A) = L(B)$}\} $$ ist entscheidbar.

Beweise

$L(A) = L(B)$ gilt genau dann, wenn jedes Wort, das in $A$ ist, auch in $B$ ist und wenn jedes Wort, das in $B$ ist, auch in $A$ ist. Dies kann man umformulieren. Bspw. darf es kein Wort geben, das in $A$ ist und nicht in $B$. Mengentheoretisch ausgedrückt bedeutet dies, dass $L(A) \cap \overline{L(B)}$ leer sein muss. Ebenso muss auch $L(B) \cap \overline{L(A)}$ leer sein, woraus insgesamt $$ (L(A) \cap \overline{L(B)}) \cup (\overline{L(A)} \cap L(B)) = \emptyset \text{ gdw. } L(A) = L(B) $$ folgt.

Hinweis zu der genau dann, wenn Beziehung

Will man sich von der Richtigkeit der obigen Aussage noch einmal genau überzeugen, gelingt der Beweis recht schnell. Sei $L(A) = L(B)$. Dann kann man auf der linken Seite überall $L(A)$ durch $L(B)$ ersetzen und erhält dann $L(B) \cap \overline{L(B)}$ und $(\overline{L(B)} \cap L(B)$, was beides offensichtlich $\emptyset$ ist. Daher gilt die linke Seite. Gilt andererseits die linke Seite, so wollen wir $L(A) = L(B)$ zeigen. Sei dazu $w \in L(A)$, dann kann nicht $w \not\in L(B)$ sein, da dann $w \in \overline{L(B)}$ gelten würde und dann $L(A) \cap \overline{L(B)}$ nicht leer wäre. Daher muss $w \in L(B)$ gelten. Entsprechend folgt für $w \in L(B)$ durch eine analoge Argumentation mit der Menge $\overline{L(A)} \cap L(B)$, dass $w \in L(A)$ gelten muss, womit insgesamt $L(A) = L(B)$ folgt.

Es ist nun mit unsere bisherigen Techniken möglich aus den DFAs $A$ und $B$ einen DFA $C$ mit $$ L(C) = (L(A) \cap \overline{L(B)}) \cup (\overline{L(A)} \cap L(B)) $$ zu konstruieren. Dazu baut man zu $A$ und $B$ jeweils einmal einen Komplementautomaten, dann mit diesen und den ursprünglichen Automaten zwei Produktautomaten und zuletzt einen Automaten, der gerade die Vereinigung akzeptiert. Es ist dann mit dem eben gezeigten $$ L(C) = \emptyset \text{ gdw. } L(A) = L(B) $$ und wir können den Leerheitstest des vorherigen Satzes nutzen, um $L(A) = L(B)$ zu entscheiden.

Im einzelnen arbeitet eine Turingmaschine, die $DFA_{=}$ bei Eingabe zweier DFAs $A$ und $B$ entscheidet, wie folgt:

Konstruiere $C$ wie oben beschrieben.
Benutze eine TM $M$, die $DFA_{\emptyset}$ entscheidet, auf $C$.
Falls $M$ akzeptiert, akzeptiere, sonst nicht.

Wichtig ist hier wieder, dass die einzelnen Schritte in endlicher Zeit möglich sind, also terminieren. Dies ist der Fall, da die einzelnen Konstruktionen, die beim ersten Schritt nötig sind, alle terminieren und da im zweiten Schritt $M$ eine Turingmaschine ist, die bei jeder Eingabe anhält. Mit dem oben ausgeführten ist dann auch klar, dass genau dann akzeptiert wird, wenn $L(A) = L(B)$ gilt. Damit entscheidet die Turingmaschine das Problem $DFA_{=}$.

Wir wollen nun noch ein weiteres Problem betrachten, das uns hilft, unsere bisherigen vier Sprachfamilien in Beziehung zu setzen.

Satz 4.3.9

Die Sprache $$ CFG_{acc} := \{ \langle G, w \rangle \mid \text{[/latex]G[/latex] ist eine CFG und generiert $w$}\} $$ ist entscheidbar.

Beweise

In den Übungsaufgaben wird gezeigt, dass zu jeder Grammatik $G$ die Sprache $L(G)$ entscheidbar ist. Damit ist dieses Problem dann leicht zu entscheiden. Sei $M_G$ die Turingmaschine, die $L(G)$ entscheidet. Bei Eingabe von $G$ und $w$ wird $M_G$ konstruiert (es ist wichtig, dass dies möglich ist, was aber der Fall ist) und dann wird $w$ einfach $M_G$ vorgelegt. Akzeptiert $M_G$ so wird akzeptiert, sonst abgelehnt.

Da es stets möglich ist $M_G$ zu konstruieren und diese dann entscheidet, ob $w \in L(G)$ gilt oder nicht, terminiert das Verfahren immer und da $M_G$ korrekt arbeitet, akzeptiert auch das hier vorgestellte Verfahren genau dann, wenn tatsächlich $w$ von $G$ generiert wird.

Mit $DFA_{acc}$ und $CFG_{acc}$ bzw. den sehr ähnlichen Fragestellungen, dass $L(A)$ und $L(G)$ für jeden DFA $A$ und jede CFG $G$ entscheidbar sind und da wir eine Turingmaschine für z.B. $\{a^n b^n c^n \mid n \in \mathbb{N}\}$ angeben können, eine Sprache, die nicht kontextfrei ist, folgt $$ \text{REG} \subset \text{CF} \subset \text{REC} \subseteq \text{RE} $$

Neben den bisher gesehenen Sprachen gibt es noch etliche weitere entscheidbare Sprachen. Diese Sprachfamilie spielt in der Informatik eine besondere Rolle, da dies die Probleme sind, die wir von einem Computer lösen lassen können. Ein Algorithmus kann bei Vorlage einer Eingabe stets entscheiden, ob diese zu der Sprache gehört oder nicht, was aufgrund der Analogie zwischen Sprachen entscheiden und Funktionen berechnen damit gleichzusetzen ist, Lösungen zu berechnen. Zwei Probleme können nun auftreten. Eine Sprache könnte aus dieser Sprachfamilie herausfallen. Dies ist deswegen problematisch, da eine Sprache, die bspw. nur aufzählbar, nicht aber entscheidbar ist, unangenehme Eigenschaften hat. Bei Vorlage eines Wortes $w$ würde eine Turingmaschine zwar anhalten und akzeptieren, wenn $w$ in der Sprache ist. Wenn $w$ aber nicht in der Sprache ist, dann arbeitet die Turingmaschine unter Umständen unendlich lange und für einen Benutzer ist das Problem, dass er nie weiß, ob vielleicht noch berechnet wird, dass $w$ in der Sprache ist oder ob die Turingmaschine nur immer weiter rechnet. Tatsächlich gibt es solche unangenehmen Probleme und tatsächlich sind sie weder selten noch unwichtig – im Gegenteil! Wir werden uns mit diesen Problemen im Abschnitt über Unentscheidbarkeit noch genauer befassen.

Ein zweites Problem betrifft die Zeit, die benötigt wird, um ein Problem zu lösen. Nur weil ein Problem entscheidbar ist, bedeutete dies nämlich nicht, dass die Zeit, die benötigt wird, um es tatsächlich zu lösen, akzeptabel ist. Brauchen wir länger zur Berechnung einer Lösung als das Universum existieren wird, so ist dies ganz bestimmt nicht akzeptabel, aber auch schon wenn eine Berechnung länger als ein paar Sekunden dauert, kann dies, je nach Anwendungsfall, nicht akzeptabel sein. Wir kommen hierauf im Kapitel zur Komplexitätstheorie zu sprechen.

Beispiele aufzählbarer Sprachen

Alle im vorherigen Abschnitt vorgestellten entscheidbaren Sprachen sind wegen $\text{REC} \subseteq \text{RE}$ auch aufzählbar. Eine weitere Sprache, die aufzählbar ist, aber für die einem auf den ersten Blick keine Möglichkeit einfällt, sie zu entscheiden, ist die folgende Sprache $TM_{acc}$.

Satz 4.3.10

Die Sprache $$ TM_{acc} := \{ \langle M, w \rangle \mid \text{$M$ ist eine TM und akzeptiert $w$}\} $$ ist aufzählbar.

Beweise

Sei $\langle M, w \rangle$ die Eingabe, wobei $M$ eine TM und $w$ ein Wort ist.

Simuliere $M$ auf $w$.
Wenn $M$ jemals einen Endzustand erreicht, akzeptiere. Lehnt $M$ ab, so lehne ab.

Man müsste sich wieder im einzelnen überlegen, wie $M$ simuliert wird, dies ist aber ähnlich wie beim DFA recht einfach. Die Rechnung einer Turingmaschine ist zwar komplizierter, aber aus algorithmischer Sicht sind lediglich mehr Fälle zu beachten. Ein wirkliches Problem stellt dies nicht dar.

Es gibt also eine Turingmaschine $M‘$ mit $L(M‘) = TM_{acc}$. Sollte bei der Simulation von $M$ auf $w$ allerdings $M$ in eine Endlosschleife geraten, so simuliert $M‘$ immer weiter. Dies ist in Ordnung, denn da $M$ nicht akzeptiert, soll $M‘$ dies auch nicht. Die Sprache wird so aber nicht entschieden, sondern nur aufgezählt. Wir werden später zeigen, dass es tatsächlich nicht möglich ist, $TM_{acc}$ zu entscheiden. Eine Aussage, die man gar nicht genug betonen kann, denn sie zeigt uns unsere ganz grundsätzlichen Grenzen bei der Arbeit mit dem Computer auf. Ist $TM_{acc}$ nicht entscheidbar, dann ist es nicht möglich einen Algorithmus zu schreiben, der uns für andere Algorithmen berechnet, ob diese bei einer bestimmten Eingabe ein bestimmtes Ergebnis liefern oder nicht.

Hinweis zum Verhältnis von Turingmaschinen und Algorithmen

Die Rolle des Algorithmus übernimmt hier die Turingmaschine $M$, die wir als Eingabe erhalten. Die Rolle der Eingabe des Algorithmus übernimmt das Eingabewort $w$ der Turingmaschine $M$ und die Rolle des Ergebnisses spielt die Frage, ob $w$ von $M$ akzeptiert wird oder nicht.

Damit sind dann ganz grundsätzliche Probleme der Verifikation von Programmen außerhalb unserer Reichweite.

Weitere Probleme, die aufzählbar sind, sind im folgenden Satz aufgelistet. Bei allen wird zum Nachweis einfach die Turingmaschine aus der Eingabe simuliert und gewartet, ob das gewünschte Ereignis wie das Anhalten der Turingmaschine oder die Ausgabe einer $0$ passiert.

Satz 4.3.11

Die Sprachen $$ TM_{halt} := \{ \langle M, w \rangle \mid \text{$M$ ist eine TM und hält auf $w$}\} \\ TM_{print0} := \{ \langle M \rangle \mid \text{gestartet auf $\lambda$ gibt $M$ irgendwann $0$ aus}\} \\ TM_{reach} := \{ \langle M, z \rangle \mid \text{es gibt eine Eingabe, bei der $M$ den Zustand $z$ besucht}\} $$ sind aufzählbar.

Bei der letzten Sprache genügt es nicht $M$ nur auf einer Eingabe zu simulieren, stattdessen ist es nötig, die Turingmaschine nach und nach auf allen Worten starten zu lassen. Dazu lässt man sie erst einen Schritt auf jedem Wort der Länge $1$ simulieren, dann einen weiteren Schritt auf jedem Wort der Länge $1$ und einen Schritt auf jedem Wort der Länge $2$, dann einen weiteren Schritt auf jedem Wort der Länge $1$ und $2$ und einen Schritt auf jedem Wort der Länge $3$ und immer so weiter. Gibt es ein Eingabewort $w$ der Länge $n$, bei dem $z$ nach $m$ Schritten besucht wird, so werden auf diese Art und Weise irgendwann auch der $m$te Schritt bei Worten der Länge $n$ simuliert und dann wird dies erkannt. Diese Technik werden wir auch bei Abschlusseigenschaften nutzen, insb. wenn wir zeigen wollen, dass die aufzählbaren Sprachen gegenüber Vereinigung abgeschlossen sind.

Abschlusseigenshaften

Bei den regulären Sprachen haben wir gesehen, dass diese gegenüber allen wichtigen Operationen abgeschlossen sind. So sind bspw. $L_1 \cup L_2$, $L_1 \cap L_2$ und $\overline{L_1}$ wieder regulär, wenn $L_1$ und $L_2$ dies sind. Bei den kontextfreien Sprachen haben wir gesehen, dass diese zwar gegenüber Vereinigung, Konkatenation und Sternbildung abgeschlossen sind, nicht aber gegenüber Durchschnitt und Komplementbildung. Man kann nun wieder fragen, wie sich dies bei den aufzählbaren und entscheidbaren Sprachen verhält? Wir betrachten hier nur die drei wichtigsten Operationen.

Satz 4.3.12

Die entscheidbaren Sprachen sind gegenüber $\cap$, $\cup$ und Komplementbildung abgeschlossen.
Die aufzählbaren Sprachen sind gegenüber $\cap$ und $\cup$ abgeschlossen. Sie sind nicht gegenüber Komplementbildung abgeschlossen.

Beweise

Der Fall der entscheidbaren Sprachen ist recht einfach. Seien $L_1$ und $L_2$ entscheidbare Sprachen und seien $M_1$ und $M_2$ Turingmaschinen, die $L_1$ bzw. $L_2$ entscheiden. Um $L_1 \cap L_2$ zu entscheiden, führt man auf einer Eingabe $w$ erst $M_1$, dann $M_2$ aus. Da beide stets halten, geht dies problemlos. Akzeptieren beide, wird akzeptiert, sonst abgelehnt.

Für $L_1 \cup L_2$ verfährt man genauso, akzeptiert aber, wenn bereits eine der beiden Turingmaschinen $M_1$ oder $M_2$ akzeptiert. Für die Komplementbildung dreht man einfach das Ergebnis um und ist dann sofort fertig.

Der Fall der aufzählbaren Sprachen ist spannender. Für $L_1 \cap L_2$ kann man wieder genauso verfahren. Problematisch ist ja ohnehin nur der Fall, dass $M_1$ oder $M_2$ unendlich lange laufen. Die ist hier aber noch nicht schlimm, denn wenn z.B. $M_1$ unendlich lange läuft und daher $M_2$ nie gestartet wird, so ist dies nicht tragisch, denn wenn $M_1$ ein Wort nicht akzeptiert, so ist dieses Wort ganz bestimmt nicht in $L_1 \cap L_2$ und es ist also egal, dass $M_1$ immer weiter arbeitet, ohne dass $M_2$ jemals gestartet wird.

Anders bei $L_1 \cup L_2$ hier funktioniert diese Methode nicht, denn sollte $M_2$ ein Wort $w$ akzeptieren, so ist das Wort in $L_1 \cup L_2$. Dies würde aber nie bemerkt werden, wenn $M_1$ das Wort $w$ nicht akzeptiert, unendlich lange arbeitet und so verhindert, dass $M_2$ je gestartet wird. Wir verfahren hier daher anders. Statt erst $M_1$ und dann $M_2$ zu starten, simulieren wir von beiden jeweils nur einen Schritt, d.h. wir simulieren zunächst einen Schritt von $M_1$ und dann einen Schritt von $M_2$. Im Anschluss simulieren wir wieder von beiden einen Schritt und so weiter. Ist ein Eingabewort $w$ in $L_1$ oder $L_2$, so wird eine der beiden Maschinen letztendlich $w$ akzeptieren. Sind beide in einer Endlosschleife, so ist auch die Maschine, die beide abwechselnd simuliert in einer Endlosschleife und hält nie, das ist dann aber nicht weiter schlimm, da wir $L_1 \cup L_2$ ja nur aufzählen wollen.

Betrachten wir zuletzt die Komplementbildung. Auch hier können wir nicht einfach wie bei den entscheidbaren Sprachen das Ergebnis umdrehen, denn eine Turingmaschine für $L_1$ könnte in Endlosschleifen geraten und dies liefert kein Ergebnis, dass eine Turingmaschine für $\overline{L_1}$ umdrehen könnte. Tatsächlich sind die aufzählbaren Sprachen auch gar nicht gegenüber Komplement abgeschlossen, so dass dieser Versuch scheitern muss. Dies folgt aus dem gleich folgenden Satz und der später noch zu zeigenden Tatsache, dass es aufzählbare Sprachen gibt, die nicht entscheidbar sind.

Satz 4.3.13

Eine Sprache $L$ ist entscheidbar genau dann, wenn $L$ und $\overline{L}$ (das Komplement von $L$) aufzählbar sind.

Beweise

Zunächst die Richtung von links nach rechts. Ist $L$ entscheidbar, dann ist $L$ auch aufzählbar. Dreht man zudem die Ergebnisse einer Turingmaschine, die $L$ entscheidet, um, so hat man eine Turingmaschine, die $\overline{L}$ entscheidet. Damit ist $\overline{L}$ dann auch aufzählbar.

Nun die spannendere Richtung von rechts nach links. Seien $A$ und $\overline{A}$ Turingmaschinen, die $L$ bzw. $\overline{L}$ akzeptieren. Eine Turingmaschine $B$, die $L$ entscheidet, kann nach der gleichen Idee wie beim obigen Beweis, dass RE gegenüber Vereinigung abgeschlossen ist, konstruiert werden. $B$ arbeitet wie folgt: Bei Eingabe von $w$ wird erst ein Schritt von $A$ simuliert, dann ein Schritt von $\overline{A}$. Im Anschluss wird wieder ein Schritt von $A$ simuliert, dann wieder einer von $\overline{A}$ und so weiter. Da entweder $w \in L$ oder $w \in \overline{L}$ gelten \emph{muss}, muss $A$ oder $\overline{A}$ akzeptieren. Akzeptiert $A$, so wird akzeptiere. Akzeptiert $\overline{A}$, so wird abgelehnt. Damit haben wir eine Maschine konstruiert, die stets anhält und stets das korrekte Ergebnis liefert, die also $L$ entscheidet.

Aus dem eben gezeigten Satz folgt, dass $\text{RE} = \text{REC}$ gilt, wenn die aufzählbaren Sprachen gegenüber Komplement abgeschlossen wären.

Warum?

Warum? Wären die aufzählbaren Sprachen gegenüber Komplement abgeschlossen, so würde für jedes $L \in \text{RE}$ auch $\overline{L} \in \text{RE}$ gelten. Der eben gezeigte Satz besagt dann aber, dass $L \in \text{REC}$ gilt. Damit hätten wir gezeigt, dass jedes $L \in \text{RE}$ auch in REC ist, dass also $\text{RE} \subseteq \text{REC}$ gilt, woraus $\text{RE} = \text{REC}$ folgt, da $\text{REC} \subseteq \text{RE}$ ja ohnehin gilt.

Da wir später noch sehen werden, dass tatsächlich $\text{REC} \subset \text{RE}$ gilt, folgt, dass die aufzählbaren Sprachen nicht gegenüber Komplement abgeschlossen sein können.

Wiederholung

Wir fassen die vergangenen Abschnitte zusammen. Wir haben die Sprachfamilie REC der entscheidbaren und die Sprachfamilie RE der aufzählbaren Sprachen eingeführt. Eine Sprache $L$ ist aufzählbar, wenn es eine Turingmaschine $M$ gibt, die $L$ akzeptiert, also eine mit $L(M) = L$. Eine Sprache ist entscheidbar, wenn es eine Turingmaschine $M$ gibt, die $L$ akzeptiert und $M$ zudem bei jeder Eingabe anhält.

Wir haben dann verschiedene entscheidbare und aufzählbare Sprachen gesehen. Die entscheidbaren Sprachen sind für die Informatik von ganz besonderer Bedeutung, da diese Sprachen Probleme sind, die durch einen Algorithmus gelöst werden können. Wenn eine Sprache entscheidbar ist, ist das also erstmal ein gutes Zeichen.

Im letzten Abschnitt haben wir uns dann noch mit Abschlusseigenschaften von REC und RE beschäftigt. Wir haben gesehen, dass REC gegenüber Vereinigung, Durchschnitt und Komplement abgeschlossen ist, RE auch gegenüber Vereinigung und Durchschnitt, nicht aber gegenüber Komplement, wobei wir für die letzte Aussage noch benötigen, dass es tatsächlich Sprachen gibt, die aufzählbar, aber nicht entscheidbar sind. Wir werden dies im nächsten Abschnitt sehen. Bisher stellt sich unser Wissen über die vier Sprachfamilien REG, CF, REC und RE so dar $$ \text{REG} \subset \text{CF} \subset \text{REC} \subseteq \text{RE} $$ Eine typische reguläre Sprache ist z.B. durch den regulären Ausdruck $a^*$ gegeben. Eine typische kontextfreie Sprache, die nicht mehr regulär ist, ist z.B. die Sprache $\{a^n b^n \mid n \in \mathbb{N}\}$. Eine typische entscheidbare Sprache, die nicht mehr kontextfrei ist, ist $\{a^n b^n c^n \mid n \in \mathbb{N}\}$. Eine typische aufzählbare Sprache, ist $TM_{acc}$ und wir werden noch sehen, dass diese nicht mehr entscheidbar ist.

Hier ein paar Fragen zur Aufzählbarkeit und Entscheidbarkeit.

Varianten der Turinmaschine

Posted On 5 Dez 2014
By fgi1
In Uncategorized

Download PDF

Bisher haben wir die deterministische Turingmaschine mit einem beidseitig unendlichem Band kennengelernt. Man kann viele Varianten der Turingmaschine einführen, von denen einige recht nützlich beim Entwurf einer Turingmaschine für eine bestimmte Sprache oder eine bestimmte Funktion sind. Wir werden nachfolgend zwei Varianten der deterministischen Maschine einführen. Die eine hat nur ein einseitig unendliches Band, die andere hat mehrere Bänder. Wir werden sehen, dass diese Maschinen äquivalent sind und können dann also je nach Fragestellung die benutzen, die uns am sinnvollsten erscheint. Äquivalent bedeutet dabei wieder, dass es zu jeder TM des einen Typs eine TM des anderen Typs gibt, so dass die gleichen Sprachen akzeptiert werden.

Definiton 4.2.1

Zwei Turingmaschinen $A$ und $B$ sind äquivalent, wenn $L(A) = L(B)$ gilt.

Im Anschluss werden wir dann so wie wir es auch bei endlichen Automaten gemacht haben noch eine nichtdeterministische Variante der Turingmaschine einführen.

Nutzung verschiedener Bänder

Die bisherige DTM hat ein Band, das in beide Richtungen unendlich ist (ein beidseitig unendliches Band). Man kann eine TM definieren, bei der das Band nur in eine Richtung unendlich ist. Diese TM startet dann in einer Konfiguration $z_0 w$ und kann das Band nicht nach links verlassen. Nach rechts hin ist das Band aber unendlich.

Definiton 4.2.2

aEine DTM mit einem einseitig unendlichem Band ist wie eine DTM mit einem zweiseitig unendlichem Band definiert, kann das Band aber nicht von der anfänglichen Startposition nach links verlassen. Nummeriert man die Zellen des Bandes durch und nennt die erste Zelle die $0$te Zelle, so kann diese Zelle nicht nach links verlassen werden (die späteren Zellen aber schon).

Es wäre nun noch die Schrittrelation anzupassen, was dadurch verkompliziert wird, dass das Band nicht nach links verlassen werden kann. Wir wollen dies hier nicht im Detail machen. Ein intuitives Verständnis dieser Maschinen genügt uns an dieser Stelle.

Dass die DTM mit einem beidseitig unendlichem Band alles kann, was die DTM mit einem einseitig unendlichem Band kann, ist wenig überraschend. Andersherum geht dies aber auch. Die beiden Formalismen sind also äquivalent.

Satz 4.2.3

Zu jeder DTM $A$ mit einseitig unendlichem Band gibt es eine äquivalente DTM $B$ mit beidseitig unendlichem Band und umgekehrt.

Wir wollen den Beweis hier nicht vollständig ausführen, aber die Beweisidee skizzieren. Spannend ist nur die Richtung zu der DTM $B$ mit einem beidseitig unendlichem Band die äquivalente DTM $A$ mit einseitig unendlichem Band zu konstruieren.

Beweisidee

Das Band von $A$ ist einseitig unendlich. Wir können also von einem $0$-ten, $1$-ten, $2$-ten usw. Feld sprechen. Der LSK ist zu Beginn auf dem $0$-ten Feld. Das Band von $B$ ist beidseitig unendlich. Hier wollen wir auch von dem Feld als $0$-ten Feld sprechen, auf dem zu Anfang der LSK ist. Rechts davon sind dann das $1$-te, $2$-te usw. Feld. Links davon wollen wir vom $-1$-ten, $-2$-ten usw. Feld sprechen.

Die Idee ist nun, dass $A$ sich auf dem $n$-ten Feld des Bandes merkt, was auf dem $n$-ten \emph{und} dem $-n$-ten Feld von $B$ steht. Dazu ist $\Gamma \times (\Gamma \cup \{*\})$ das Bandalphabet von $A$ ($\Gamma$ ist das Bandalphabet von $B$). Man sagt hierzu, dass man das Band in \emph{Spuren} eingeteilt hat. Das Symbol $*$ wird nur an einer Stelle benötigt, nämlich für das $0$-te Feld zudem es keinen negativen Partner gibt. $A$ merkt sich zusätzlich im Zustand, ob $B$ gerade im positiven oder negativen Bereich seines Bandes ist. Zustände von $A$ sind also $[z,P]$ und $[z,N]$ (wobei $z$ aus $Z_B$, der Zustandsmenge von $B$, ist).

$A$ arbeitet nun wie $B$ und ändert bei $(x,y) \in \Gamma \times \Gamma$ nur das Element was durch das $P$ bzw. $N$ im Zustand vorgegeben wird. Ist man z.B. im Zustand $[z,P]$ und liest $(x,y)$, dann wird geguckt, was $B$ in $z$ bei $x$ machen würde und entsprechend das $x$ in $(x,y)$ geändert. Der Zustandswechsel und das Bewegen nach links und rechts des LSK ist entsprechend. Nur bei dem $0$-ten-Feld muss man aufpassen, da hier ein Wechsel von $P$ zu $N$ oder andersherum auftreten kann. Dies ist aber auch einfach durch die \“Uberführungsfunktion von $A$ abzudecken. Ist man z.B. in $[z,P]$ auf dem Symbol $(x,*)$ und bewegt $B$ den LSK nach links, so geht man nun in den negativen Bereich des Bandes, d.h. $A$ wechselt in einen Zustand $[z‘,N]$ und bewegt den LSK nach rechts.

Dies schließt die Konstruktion ab. Es ist dann nicht schwierig zu zeigen, dass tatsächlich [/latex]L(A) = L(B)[/latex] gilt. Hierzu betrachtet man lediglich die Erfolgsrechnungen von $A$ bzw. von $B$ und argumentiert, dass dies auch Erfolgsrechnungen in der jeweils anderen Maschine sind, wenn man sich auf das durch $N$ bzw. $P$ im Zustand vorgegebene Element von $(x,y)$ beschränkt.

Eine weitere Variante, diesmal aber mit mehr Bändern, ist die $k$-Band off-line Turingmaschine. Diese hat neben dem bisherigen Eingabeband, auf dem ja auch gearbeitet wurde, nun $k$ weitere Arbeitsbänder und ein Ausgabeband. Zudem wird die Nutzung des Eingabebandes und des Ausgabebandes eingeschränkt.

Definiton 4.2.4 (k-Band off-line Turingmaschine)

Eine $k$-Band off-line Turingmaschine (kurz $k$-Band TM oder auch Mehrband-TM) hat

$k$ beidseitig unendliche Arbeitsbänder mit jeweils einem eigenen LSK,
ein Eingabeband, auf dem sie ausschließlich lesen kann, aber den Lese-Kopf dabei in beide Richtungen bewegen darf und
ein Ausgabeband, auf dem sie nur schreiben und den Schreibkopf ausschließlich von links nach rechts bewegen darf.

Es wären wieder die Definitionen für Konfiguration und Schrittrelation anzupassen, aber wir wollen auch hier darauf verzichten. Ein intuitives Verständnis der Arbeitsweise genügt auch hier. Die $k$-Band TM liest stets ein Symbol vom Eingabeband und ein Symbol vom jedem Arbeitsband. Sie kann dann den Kopf auf dem Eingabeband bewegen, mit den Köpfen auf dem Arbeitsband neue Symbole schreiben und diese Köpfe bewegen und sie kann (muss) aber nicht etwas auf das Ausgabeband schreiben, wobei dann der Kopf dort automatisch nach rechts bewegt wird. Diese TM ist sehr praktisch, wenn man von einer TM nur deren Arbeitsweise beschreiben will. Sie ist auch wieder äquivalent zur ursprünglichen DTM.

Satz 4.2.5

Zu jeder $k$-Band off-line Turing-Maschine $A$ mit $k \geq 1$ gibt es eine äquivalente DTM $B$ mit nur einem Band und umgekehrt.

Wieder ist die Richtung von $B$ zu $A$ sofort einsichtig, da man die Fähigkeiten der TM $A$ quasi nicht nutzt. Man liest einmal die Eingabe vom Band und notiert sie auf einem Arbeitsband. Dort arbeitet man dann so wie mit $B$ und zuletzt schreibt man ggf. den Bandinhalt noch auf das Ausgabeband. Die Rückrichtung ist interessanter und wir wollen die Beweisidee wieder skizzieren

Beweisidee

Die Idee der Konstruktion ist im Grunde wie eben. Nur teilen wir das Band der $1$-Band TM $B$ nun in mehr als zwei Spuren ein. Wir haben eine Spur für das Eingabeband von $A$, jeweils eine für jedes Arbeitsband und eine für das Ausgabeband. Da $A$ außerdem mehr Lese-Schreib-Köpfe hat, muss man für jede Spur markieren, wo der LSK ist, z.B. indem man für jedes Symbol $x$ noch ein Symbol $x‘$ einführt, das bedeutet, dass hier der LSK ist. Die $1$-Band TM muss dann oft über ihr eines Band wandern, um in jeder Spur die richtige Stelle zu finden und sich dann zu entscheiden, welche Aktion auszuführen ist. Dann muss sie noch mal mehrmals über das Band wandern und jede Stelle aktualisieren.

Damit wissen wir, dass deterministische Turingmaschinen mit einem Band, deterministische Turingmaschinen mit $k$ Arbeitsbändern und deterministische Turingmaschinen mit einem nur einseitig unendlichem Band äquivalent sind. Wir können also je nach Aufgabe eine geeignet erscheinende auswählen. Wir wollen dies hier so machen, dass wir eine Turingmaschine mit einem Band, das in beide Richtungen unendlich ist, nehmen, wenn wir eine TM konstruieren wollen und explizit das Zustandsübergangsdiagramm angeben wollen. Ein Beispiel dafür ist die Turingmaschine für $L = \{w w^{rev} \mid w \in \{0,1\}^*\}$ aus dem vorherigen Abschnitt.

Mit einer $k$-Band off-line TM wollen wir arbeiten, wenn wir nur die Funktionsweise einer TM beschreiben wollen, wenn wir also auf einer gewissen Abstraktionsebene arbeiten wollen. Dies haben wir z.B. bei der Berechnung der Funktion $f(x) = x – 1$ im vorherigen Abschnitt gemacht. Dort hat allerdings ein Band ausgereicht.

Nutzung von Nichtdeterminismus

Die bisherigen Varianten waren Variationen, die insb. die Nutzung der Bänder betraf, aber weiterhin deterministisch waren. Wie bei DFAs ist es auch bei Turingmaschinen möglich eine nichtdeterministische Variante einzuführen. Hierzu müssen wir nur die \“Uberführungsfunktion anpassen, so dass für ein Tupel $(z,x) \in Z \times \Gamma$ mehrere Folgekonfigurationen möglich sind.

Definiton 4.2.6 (Nichtdeterministische Turingmaschine)

Eine Turingmaschine $M = (Z, \Sigma, \Gamma, K, z_0, Z_{end})$ heißt nichtdeterministische Turingmaschine (kurz NTM), wenn es zu jedem Paar $(z,x) \in Z \times \Gamma$ eine endliche Anzahl von Übergängen gibt. D.h. es ist $$ K \subseteq Z \times \Gamma \times \Gamma \times \{L, R, H\} \times Z $$ bzw. $$ \delta: Z \times \Gamma \rightarrow 2^{\Gamma \times \{L,R,H\} \times Z} $$ alles andere ist wie bei der DTM definiert.

Man könnte wie bei NFAs auch mehrere Startzustände erlauben. Dies ist aber nicht nötig, da eine NTM als erstes nichtdeterministisch in mehrere Folgezustände gehen könnte, ohne den Bandinhalt oder die Position des LSK zu ändern. Wir belassen es daher so, dass die NTM nur einen Startzustand hat.

Die NTM akzeptiert dann ein Eingabewort $w$ genau dann, wenn es \emph{mindestens eine} Erfolgsrechnung auf $w$ gibt.

Definiton 4.2.7 (Akzeptierte Sprache einer NTM)

Konfigurationen einer NTM sind wie bei der DTM definiert. Die Konfigurationsübergänge werden so angepasst, dass nicht $\delta(z,x) = (x‘,B,z‘)$ gelten muss, sondern $(x‘,B,z‘) \in \delta(z,x)$. Darauf aufbauend können dann Rechnung und Erfolgsrechnung und die akzeptierte Sprache analog zu der Definitionen für DTMs definiert werden. Insb. akzeptiert eine NTM genau dann ein Wort $w$, wenn es von $z_0 w$ mindestens eine Rechnung gibt, die in eine Konfiguration $u z_e v$ mit $z_e \in Z_{end}$ führt.

Bei endlichen Automaten haben wir gesehen, dass der Nichtdeterminismus keine entscheidenden Vorteile bringt. Bei Turingmaschinen sieht dies anders aus. Wir betrachten als Beispiel folgendes Problem.
Eingabe: & Ein ungerichteter Graph $G = (V,E)$ und ein $k \in \mathbb{N}$.
Frage: & Hat $G$ eine $k$-Clique?

Eine $k$-Clique sind dabei $k$ Knoten des Graphen, die alle paarweise miteinander verbunden sind. Ein Dreieck ist z.B. eine $3$-Clique. Wir wollen dieses Problem mit einer Turingmaschine lösen. Die Eingabe für die Turingmaschine ist dabei die Zahl $k$ gefolgt von einer Liste der Knoten und der Kanten (letzteres als Tupel zweier Knoten).

Pause to Ponder: Wie löst man nun dieses Problem mit einer DTM und wie mit einer NTM?

Mit einer DTM können wir nach und nach alle $k$-elementigen Teilmengen von $V$ durchgehen und prüfen, ob die aktuelle Teilmenge eine $k$-Clique ist. Es gibt allerdings recht viele $k$-elementigen Teilmengen von $V$, weswegen dieses Verfahren recht lange dauert. Aber immerhin funktioniert es.

Wie können wir dieses Problem mit einer NTM lösen? Hierzu bedienen wir uns massiv des Nichtdeterminismus bzw. des Ratens. Um dies klarer zu machen betrachten wir folgende NTM. Diese kann bei jedem Zustandswechsel nichtdeterministisch eine $0$ oder eine $1$ auf das Band schreiben. Man sagt hier auch, das die NTM eine $0$ bzw. eine $1$ rät und dann je nachdem in der Nachfolgekonfiguration ist, in der sie eine $0$ bzw. eine $1$ auf das Band geschrieben hat.

Nach drei Schritten ergibt sich der folgende Konfigurationsbaum, der alle nichtdeterministisch erreichbaren Konfigurationen darstellt. Dieser Baum wird sehr groß.

Ein Pfad in diesem Baum ist aber recht kurz. Dieses Raten nutzen wir nun aus, um eine Mehrband-NTM zu entwickeln, die das Clique-Problem löst. Die Mehrband-NTM arbeitet wie folgt: Zunächst zählt sie die Anzahl der Knoten des Graphen. Sei dies $n$. Nun rät sie auf einem Arbeitsband $n$-mal nichtdeterministisch eine $0$ oder eine $1$.

Hinweis zum Raten

Hier sei am Rande erwähnt, dass die NTM sich irgendwo speichern muss, dass sie $n$-mal raten soll. Sie kann z.B. einen Zähler initialisieren und diesen auf $n$ setzen. Nach jedem raten einer Zahl vermindert sie dann den Zähler um eins und wenn der Zähler $0$ erreicht, ist sie fertig.

Nun ist die NTM nichtdeterministisch in $2^{n}$ Konfigurationen. Die Konfigurationen unterscheiden sich dabei nur in der gerade erstellten Bandinschrift des Arbeitsbandes. Auf diesem stehen die Zahlen zwischen $0^n$ und $1^n$, was gerade $2^n$ Zahlen sind. In jeder dieser Konfigurationen geht es jetzt deterministisch weiter, d.h. wir benötigen den Nichtdeterminismus nicht mehr. Im Grunde machen wir nämlich nur das, was wir oben bereits bei der beschriebenen DTM gemacht haben. Von den $n$ eben geratenen Zahlen bedeutet eine $1$ an $i$-ter Stelle, dass der $i$-te Knoten zur Clique gehört (bzw. dass dies geraten wird) und eine $0$, dass er dies nicht tut. Die NTM überprüft nun zunächst, ob die $1$ gerade $k$-mal vorkommt. Im Anschluss wird überprüft, ob diese $k$ Knoten tatsächlich eine $k$-Clique bilden, d.h. für je zwei davon wird geprüft, ob es eine Kante gibt, die sie verbindet. Falls dies gelingt, wird akzeptiert, sonst nicht. Hat der Graph tatsächlich mindestens eine $k$-Clique, so gibt es eine Rechnung der NTM, die diese rät und somit findet. Damit löst die vorgestellt Mehrband-NTM das Problem. Eine Rechnung ist dabei aber viel kürzer als die Rechnung der DTM. Wir kommen auf diesen wichtigen Unterschied später im Rahmen der Komplexitätstheorie zu sprechen.

Hinweis

Man kann an obigen Beispiel auch gut sehen, wie man die Arbeitsweise einer TM beschreiben kann, ohne das Zustandsübergangsdiagramm anzugeben. Die Beschreibung wird dann abstrakter, muss aber genau genug bleiben, um nachvollzogen werden zu können und es dürfen nur Operationen vorkommen, die man tatsächlich auch mit einer (ggf. sehr komplizierten TM) machen kann. Nur wenn diese Beschreibung dennoch exakt bleibt, ist es dann möglich über die Korrektheit der Turingmaschine zu argumentieren. Es genügt also bei Turingmaschinen die Arbeitsweise abstrakt zu beschreiben, statt ein Diagramm anzugeben. Dies muss aber exakt und hinreichend genau genug geschehen, so dass damit argumentiert werden kann.

Wenn man nun die DTM und die NTM für obiges Problem vergleicht, dann ist der Kern bei der NTM, dass diese eine mögliche Lösung nichtdeterministisch rät und dann überprüft, ob diese vermutete Lösung tatsächlich eine ist. Die DTM hingegen kann nur nacheinander alle möglichen Lösungen durchgehen. Man kann an dieser Stelle also fragen, ob eine DTM stets alles kann, was eine NTM kann. Oben können beide das Problem lösen, auch wenn die DTM dies viel langsamer tut. Dennoch erschien die NTM mächtiger. Daher die wichtige Frage:

Pause to Ponder: Lässt sich jede NTM durch eine DTM simulieren?

Tatsächlich sind die beiden Modelle wieder äquivalent. Dabei ist die Richtung von DTM zu NTM wieder klar. Man nutzt den Nichtdeterminismus nicht und kann so ganz einfach eine NTM konstruieren, die die gleiche Sprache akzeptiert wie eine gegebene DTM. Für die Rückrichtung erinnern wir noch einmal an obiges Beispiel einer NTM mit dem zugehörigen Konfigurationsbaum.

Ein anderes Beispiel ist die folgende nichtdeterministische Turingmaschine.

Auf dem Eingabewort $abab$ ergibt sich der folgende Konfigurationsbaum.

Die Idee bei der Konstruktion ist nun, dass es zu jedem Knoten in einem Konfigurationsbaum nur endlich viele Nachfolger geben kann, da die Überführungsfunktion der NTM zwar verschiedene Möglichkeiten anbieten kann, bei einem Zustand, in dem die NTM ist, und Symbol, das sie liest, in eine Nachfolgekonfiguration zu gehen, dies aber stets endlich viele sind. Dieser Konfigurationsbaum kann nun von einer DTM Ebene für Ebene aufgebaut werden und so eine Breitensuche in diesem Baum ausgeführt werden. Tritt dabei eine Konfiguration auf, die einen Endzustand enthält, so wissen wir, dass die NTM akzeptieren würde. In diesem Fall akzeptiert auch die DTM. Ansonsten wird der Baum immer weiter aufgebaut. Wir führen die Idee nachfolgend noch etwas genauer aus.

Satz 4.2.8

Jede von einer NTM akzeptierte Sprache kann auch von einer DTM akzeptiert werden und umgekehrt.

Beweisidee

Die Richtung von DTM zu NTM ist klar. Für die Rückrichtung beobachten wir, dass eine Konfiguration $c_1$ einer NTM, zwar mehrere (nichtdeterministische) Nachfolgekonfiguration haben kann, dass dies aber stets nur endlich viele sind. Seien diese mit $c_{1,1}, c_{1,2}, \ldots, c_{1,r}$ bezeichnet. Man kann diese Konfigurationen als Baum darstellen mit $c_1$ als Wurzel und $c_{1,1}, \ldots, c_{1,r}$ als Kinder von $c_1$. Die $c_{1,i}$ haben dann wieder (endlich viele) Kinder $c_{1,1,1}, \ldots, c_{1,1,j_1}$ und $c_{1,2,1}, \ldots, c_{1,2,j_2}$ usw., die die dritte Ebene im Baum bilden.

Die DTM kann nun die NTM simulieren. Dazu notiert sie auf einem Band (wir konstruieren eine Mehrband-DTM) die Startkonfiguration der NTM. Dann werden alle Nachfolgekonfigurationen dieser Startkonfiguration notiert und die Startkonfiguration gelöscht. Nun wird die erste der eben ermittelten Nachfolgekonfigurationen durch ihre Nachfolgekonfigurationen ersetzt. Dann die zweite der zuerst ermittelten Nachfolgekonfigurationen durch ihre Nachfolgekonfigurationen usw. Auf diese Weise wird der Baum Ebene für Ebene aufgebaut. Wird dabei eine Konfiguration erzeugt, die einen Endzustand enthält, so akzeptiert die DTM.

Wichtig dabei ist, dass nachdem z.B. die Konfiguration $c_1$ durch ihre Nachfolgekonfigurationen $c_{1,1}, \ldots, c_{1,r}$ ersetzt wurde, als nächstes mit $c_2$ weitergemacht wird (nicht mit $c_{1,1}$). Auf diese Weise wird erst eine Ebene des Baumes vollständig aufgebaut, bevor in die nächste gegangen wird. So ist sichergestellt, dass man eine Konfiguration mit Endzustand findet, wenn eine existiert. Existiert nämlich eine, so muss es eine in z.B. der $i$-ten Ebene des Baumes geben und diese erreicht man. Wandert man anders durch den Baum (macht z.B. oben mit $c_{1,1}$ weiter, statt mit $c_2$ und wandert so zunächst in die Tiefe des Baumes), so besteht die Gefahr, dass man Konfigurationen einer unendlich langen Rechnung der NTM erzeugt und nie zu einer anderen Rechnung gelangt, in der vielleicht akzeptiert wird.

So konstruiert, akzeptiert die DTM genau dann, wenn es eine Rechnung der NTM gibt bei der akzeptiert wird und damit also genau dann, wenn die NTM akzeptiert.

Damit haben wir gesehen, dass auch die nichtdeterministische Turingmaschine nicht mächtiger ist als die deterministische. Wie bei NFAs ist es aber oft einfacher eine NTM anzugeben als eine DTM. Außerdem werden wir später sehen, was in diesem Abschnitt schon angedeutet wurde, dass die NTM Probleme scheinbar schneller lösen kann, als eine DTM.

Wiederholung

Wir wiederholen die Ergebnisse dieses Abschnittes. Wir haben zunächst verschiedene Varianten der vorher eingeführten deterministischen Turingmaschine eingeführt. Wir haben die deterministische Turingmaschine mit einem einseitig unendlichem Band und eine $k$-Band off-line Turingmaschine gesehen und argumentiert, dass diese äquivalent zur deterministischen Turingmaschine mit einem beidseitig unendlichem Band sind. Bei den Beweisen war die Idee, ein Band in Spuren einzuteilen, zentral.

Danach haben wir die nichtdeterministische Turingmaschine eingeführt, die wie der NFA aus einer Konfiguration nichtdeterministisch in verschiedene andere wechseln kann. Wir haben am Beispiel des Clique-Problems gesehen, wie die NTM ein Problem scheinbar deutlich schneller lösen kann, haben aber auch gesehen, dass die DTM dieses Problem, wenn auch scheinbar langsamer, auch lösen kann. Im Anschluss haben wir dann noch gesehen, dass jede NTM von einer DTM simuliert werden kann, die beiden Modelle also auch äquivalent sind. Die Beweisidee war hier, den Konfigurationsbaum der NTM Ebene für Ebene aufzubauen und so eine Breitensuche in diesem Baum mit der DTM zu machen.

Hier ein paar Fragen zu Varianten von Turingmaschinen.

Die Church-Turing-These

Posted On 4 Dez 2014
By fgi1
In Uncategorized

Download PDF

Wir haben im letzten Abschnitt gesehen, wie eine DTM eine Funktion berechnet und haben mehrere Beispiele gesehen, wie eine DTM spezielle Funktionen berechnet. Man kann sich vielleicht bereits vorstellen, dass neben der Addition und der Subtraktion auch alle anderen Rechenoperationen möglich sind, die ein Mensch auf einem Papier machen kann. Im Grunde genommen folgt jede Rechnung, die ein Mensch auf einem Papier machen kann, einer genauen Vorschrift und ist damit ein Algorithmus. Dies lässt sich dann auch in eine Turingmaschine kodieren, die damit alles machen kann, was ein Mensch machen kann. Die Church-Turing-These, die wir eingangs schon erwähnten, besagt genau dies. Sie ist so bedeutend, dass sie uns diesen eigenen Abschnitt wert ist. Die Church-Turing-These besagt folgendes:

Alles was intuitiv berechenbar ist, d.h. alles, was von einem Menschen berechnet werden kann, das kann auch von einer Turingmaschine berechnet werden. Ebenso ist alles, was eine andere Maschine berechnen kann, auch von einer Turingmaschine berechenbar.

Für uns von besonderer Bedeutung ist auch der Umkehrschluss:

Was eine Turingmaschine nicht berechnen kann, kann auch kein Mensch berechnen!

Da die Turingmaschine ein formales Modell ist, kann man exakt argumentieren, was diese nicht kann bzw. versuchen dies zu tun. Gelingt dies, so hat man eine Funktion gefunden, die auch ein Mensch nicht berechnen kann. Wir werden später sehen, dass sich hier ganz grundlegende Problemstellungen der Informatik verstecken, die einer algorithmischen Lösung also nicht zugänglich sind.

Hier ein paar Fragen zur Church-Turing-These.

Funktionen berechnen

Posted On 3 Dez 2014
By fgi1
In Uncategorized

Download PDF

Bisher haben wir mit Turingmaschinen so wie mit den bisherigen Automatenmodellen Sprachen akzeptiert. Eingangs haben wir aber gesagt, dass die Turingmaschine insbesondere als Modell für das Berechenbare dienen soll. Tatsächlich kann man mit Turingmaschinen auch Funktionen berechnen. Dies ist auch gar nicht so überraschend, denn wenn wir z.B. zwei Zahlen addieren wollen, dann können wir diese Zahlen ja bspw. binär kodieren, was zwei Worte über dem Alphabet $\{0,1\}$ ergibt. Das Ergebnis kann ebenfalls binär kodiert werden, so dass die DTM dann eine Wortfunktion $\Sigma^* \rightarrow \Sigma^*$ berechnet mit z.B. $\Sigma = \{0,1,\$\}$, wobei das Dollarzeichen als Trennsymbol zwischen den beiden Eingabeargumenten dient. Kurz gesagt ist es wenig überraschend, dass die TM Funktionen berechnen kann, weil wir die Argumente einer Funktion ebenso wie das Bild kodieren können, ganz so wie wir Menschen das ja auch machen, indem wir das Symbol $3$ für die Zahl $3$ nehmen.

Will man dies genau definieren, so muss man festlegen, wie die DTM startet und wie sie enden soll, wenn sie eine Funktion berechnet. Wir definieren dies wie folgt.

Definiton 4.1.5 (Turing-berechenbare Funktionen)

Sei $\Sigma$ ein Alphabet und $f: \Sigma^* \rightarrow \Sigma^*$ eine (möglicherweise partielle) (Wort-)Funktion. $f$ heißt Turing-berechenbar oder kürzer berechenbar oder auch partiell rekursiv genau dann, wenn es eine DTM $A$ gibt mit: $$ z_0 w \vdash^* z_e v \text{ für ein $z_e \in Z_{end}$ gdw. } f(w) = v $$

Wir verlangen also, dass die DTM in $z_0 w$ startet und in $z_e v$ endet, wenn $f(w) = v$ ist und andersherum. Ist $f$ auf einem Wert $w‘$ nicht definiert, so wird auch nicht gesagt, was die TM tut. Sie sollte nur nicht in einer Konfiguration $z_e v$ enden, da das ja $f(w‘) = v$ impliziert. Sinnvollerweise macht man das so, dass die DTM in einem solchen Fall in einen Zustand geht, der einen Fehler signalisiert.

Man kann das Berechnen von Funktionen noch explizit für Funktionen definieren, die mit natürlichen Zahlen arbeiten.

Definiton 4.1.6

Eine (partielle) Funktion $f: \mathbb{N}^r \rightarrow \mathbb{N}^s$ heißt (Turing-)berechenbar oder partiell rekursiv genau dann, wenn es eine DTM gibt mit
$$ z_0 0^{m_1+1} 1 0^{m_2 + 1} 1 \ldots 1 0^{m_r+1} \vdash^*
z_e 0^{n_1+1} 1 0^{n_2 + 1} 1 \ldots 1 0^{n_s+1} $$
$$genau~dann,~wenn$$
$$ f(m_1, m_2, \ldots, m_r) = (n_1, n_2, \ldots, n_s) $$
und der Funktionswert definiert ist.

Die DTM arbeitet in diesem Fall also mit dem Alphabet $\{0,1\}$ und kodiert die einzelnen Argumente von $f$ unnär, d.h. eine Zahl wie z.B. $4$ wird durch vier $0$en kodiert. Hier genauer sogar durch vier plus eine, damit man die Zahl $0$ mit einer $0$ ausdrücken kann, die Zahl $1$ dann mit zweien usw.

Häufig braucht man obiges aber gar nicht, sondern arbeitet mit Wortfunktionen wie in der ersten Definition. Hat man eine Funktion, die mit natürlichen Zahlen arbeitet, dann kodiert man die Zahlen i.A. ohnehin binär und nicht unnär. Man kann dann wie eingangs erwähnt mit einem Alphabet wie $\{0,1,\$\}$ arbeiten. Eine DTM würde dann z.B. bei der Additionsfunktion für $f(9,4) = 13$ mit der Eingabe $1001\$100$ beginnen und $1101$ berechnen, also gerade die Zahlen in Binärkodierung, nur dass dies dann je nach Sichtweise Binärzahlen oder eben Worte über dem Alphabet $\{0,1\}$ sind.

Beispiel

Als Beispiel wollen wir eine DTM beschreiben, die die Funktion $f(x) = x-1$ berechnet. Dabei sei $x$ eine natürliche Zahl, die in Binärkodierung gegeben ist. Wir wollen also eine DTM beschreiben, die die Wortfunktion von $x$ nach $f(x)$ berechnen.

Die DTM beginnt in der Konfiguration $z_0 x$ und arbeitet wie folgt:

Fahre zum am weitesten rechts stehenden Zeichen von $x$.
Ist dies eine $1$, schreibe eine $0$ und fahre bei Schritt $4$ fort.
Ist dies eine $0$, schreibe eine $1$, gehe ein Feld nach links und mach bei Schritt $2$ weiter.
Fahre ganz nach links und gehe in einen Endzustand.

Die DTM setzt gerade das schriftliche subtrahieren von $1$ um. Man beachte noch, dass im letzten Schritt ganz nach links gefahren wird, so dass wir in einer Konfiguration $z_e y$ enden, wobei $y = x + 1$ ist (bzw. Worte, die dies ausdrücken) und $z_e$ ein Endzustand ist.

Aus obiger Beschreibung lässt sich leicht das Zustandsübergangsdiagramm einer DTM gewinnen. Man muss lediglich auf Dinge achten, wie dass man im ersten Schritt über alle Symbole rüber liest, bis man auf ein $\#$ trifft, dann geht man mit dem LSK wieder nach links und ist nun auf dem letzten Symbol von $x$. Entsprechendes passiert bei dem letzten Schritt. Hier ist es dann nützlich, dass das Band in \emph{beide} Richtungen unendlich ist.

Funktionen wie $f(x) = x+y$ kann man ähnlich berechnen. Eine DTM könnte zunächst von $x$ das am weitesten rechts stehende Symbol lesen, dann von $y$ und sich beides im Zustand merken. Weiter rechts wird dann das Ergebnis aufgebaut. Dann werden die nächsten Symbole von $x$ und $y$ gelesen und das Ergebnis weiter aufgebaut. Im Zustand kann man sich zudem einen eventuellen \"Ubertrag merken. Zum Schluss muss man dann, um der Definition zu entsprechen, noch das Band so aufräumen, dass $x$ und $y$ gelöscht sind, nur das Ergebnis auf dem Band steht und der LSK ganz links von diesem steht.

Im Grunde genommen ist das Arbeiten mit einer DTM also wie das Arbeiten mit einer (sehr) eingeschränkten Programmiersprache.

Ein komplizierteres Beispiel

Als zweites Beispiel wollen wir eine kompliziertere Funktion berechnen. Wir wollen eine DTM konstruieren, die die Funktion $f(w) = w^{rev}$ für $w \in \{0,1\}^*$ berechnet, also eine DTM, die ein Eingabewort umdreht. Als Mensch würde man das Wort von hinten anfangen zu lesen und dann von rechts nach links lesen und das Gelesene Symbol für Symbol woanders von links nach rechts aufbauen. Genau diese Idee können wir auch in eine Turingmaschine kodieren.

Die DTM setzt folgende Idee bei Eingabe eines Wortes $w$ um:

Marker $\$$ sowohl links als auch rechts vom Wort $w$ setzen.
Lese letztes Symbol von $w$ und ersetze es durch $\#$.
Wandere nach rechts über das $\$$ herüber und speichern das Symbol dort. (Im Zustand merken, welches Symbol zu schreiben ist.)
Wiederhole dies, d.h. lösche das Wort $w$ von rechts nach links, Buchstabe für Buchstabe und baue das Wort $w^{rev}$ rechts davon und von links nach rechts Buchstabe für Buchstabe auf.
Zu Beachten:
- bei $w$ muss über die schon gelöschten Buchstaben (d.h. über die $\#$) rüber gelesen werden; bei $w^{rev}$ muss über das schon geschriebene Teilwort herübergelesen werden.
$w$ wurde zu Ende gelesen, wenn man auf das zweite $\$$ trifft.
Lösche die beiden $\$$ und bewege den Kopf an den Anfang von $w^{rev}$.

Die schon recht komplizierte DTM ist nachfolgend abgebildet.

Man beachte, wie sich die in der Idee beschriebene Schleife in der DTM im Kreis $z, z_1, z_1', z'$ bzw. $z, z_0, z_0', z'$ wieder findet.

Es ist nun noch genauer zu begründen, dass tatsächlich $z_s w \vdash^* z_e w^{rev}$ genau dann, wenn $f(w) = w^{rev}$ gilt. Da $f$ total ist, genügt es zu zeigen, dass die Turingmaschine in $z_s w$ gestartet, stets in der Konfiguration $z_e w^{rev}$ endet. Dazu genügt es an dieser Stelle die Arbeitsweise detailliert zu beschreiben. Wir werden dabei nämlich merken, dass die DTM nie blockiert und stets aus $w$ das Spiegelwort macht, wie gewünscht. Wir beachten zuerst, dass der Sonderfall des leeren Wortes durch die Kante von $z_s$ nach $z_e$ abgedeckt ist. Hat $w$ also mindestens die Länge $1$, dann arbeitet die Turingmaschine wie folgt. Zunächst macht sie einen Schritt nach links und setzt in $z_{LB}$ die linke Begrenzung. Dann geht sie in $z_{RB}$ über $w$ herüber und setzt die rechte Begrenzung. In $z$ angekommen ist die Konfiguration nun also stets $\$vzx\$$ mit $vx = w$. Der LSK ist also über dem letzten Symbol von $w$. Nun verfährt die DTM wie folgt. Das letzte noch nicht gelöschte Symbol von $w$ wird von rechts gesucht (daher die Schleife an $z$). Wird eine $1$ gefunden, so wird nach $z_1$ gegangen, bei einer $0$ nach $z_0$. Hier wird nun in $z_1$ (bzw. $z_0$) über die schon gelöschten Symbole von $w$ gelesen, bis der Grenzmarker $\$$ gefunden wird. In $z_1'$ bzw. $z_0'$ wird über das schon konstruierte Teilwort von $w^{rev}$ gelesen bis das Ende gefunden wird. Hier wird dann eine $1$ bzw. $0$ angefügt und nach $z'$ gewechselt. Man beachte, dass das $i$-te Symbol von \emph{rechts} von $w$ an die $i$-te Stelle von \emph{links} vom bisher aufgebauten Teilwort gesetzt wird. Daher wird hier genau $w^{rev}$ konstruiert. In $z'$ wird nun wieder über das bereits konstruierte Teilwort von $w^{rev}$ gelesen, dann der Wechsel nach $z$ gemacht und dort wieder über das bereits gelöschte Teilwort von $w$ gelesen. Dies wird in einer Schleife wiederholt bis irgendwann $w$ komplett gelöscht ist. Dies wird dadurch bemerkt, dass in $z$ der erste Grenzmarker (das links von $w$ positionierte $\$$) gefunden wird. Dieser wird dann gelöscht und nach $z''$ gewechselt, wo der andere Grenzmarker gesucht wird und ebenfalls gelöscht wird. Die DTM gelangt so stets in die Konfiguration $z_e w^{rev}$, was den Beweis abschliesst, da die TM nur genau so und nicht anders arbeiten kann, also stets bei jedem Wort $w$ genau das Wort $w^{rev}$ konstruiert und in der Konfiguration $z_e w^{rev}$ endet.

Wir wollen abschließend noch darauf eingehen, dass, obwohl unterschiedlich definiert, das Akzeptieren von Sprachen und das Berechnen von Funktionen sehr ähnlich sind. Akzeptiert eine Turingmaschine eine Sprache $L$, so tut sie im Grunde nichts anderes als die charakteristische Funktion von $L$ zu berechnen.

Hinweis zur charakteristischen Funktion

Die charakteristische Funktion einer Menge $M$ ist wie folgt definiert $$ \chi_M(x) = 1 \text{ gdw. } x \in M $$ Für ein $x \in M$ ist also $\chi_M(x) = 1$ und für ein $x \not\in M$ ist $\chi_M(x) = 0$. Akzeptiert eine Turingmaschine also ein Wort $w$ einer Sprache, so müsste sie lediglich, das Band löschen und eine $1$ auf das Band schreiben, um $\chi_M(w)$ berechnet zu haben. Ein Problem ist, dass bei Worten, die nicht in der Sprache sind, die Turingmaschine in eine Endlosschleife geraten kann und dann kann sie keine $0$ auf das Band schreiben. Wir kommen darauf später bei den entscheidbaren und unentscheidbaren Sprachen zu sprechen.

Berechnet eine Turingmaschine andersherum eine Funktion $f: M \rightarrow N$, so kann man leicht eine Turingmaschine konstruieren, die die Sprache $L = \{ (x, f(x)) \mid x \in M \}$ akzeptieren soll (hierzu müssen ggf. $M$ und $N$ geeignet kodiert werden).

Nehmen wir einmal $f(x,y) = x+y$ als Beispiel. Eine Turingmaschine, die diese Funktion berechnet, würde in einer Konfiguration $z_0 x \$ y$ starten und in einer Konfiguration $z_e f(x,y)$ enden. Will man lieber über das Akzeptieren von Sprachen sprechen, was uns insbesondere in der Komplexitätstheorie nützen wird, so betrachtet man stattdessen die Sprache $L = \{ (x,y,z) \mid x+y = z \}$. Hat man bereits eine Turingmaschine, die $f$ berechnet, lässt sich leicht eine konstruieren, die $L$ akzeptiert. Die neue Turingmaschine benutzt die alte als Subprogramm, um $x+y$ zu berechnen und vergleicht das Ergebnis mit $z$. Sie akzeptiert genau dann, wenn dieser Vergleich positiv ist.

Wiederholung

Wir fassen wieder zusammen. In diesem Abschnitt haben wir gesehen, dass Turingmaschinen nicht nur Sprachen akzeptieren können, sondern, dass sie auch Funktionen berechnen können. Die Argumente und Bilder der Funktion müssen nur geeignet kodiert werden, so dass die Turingmaschine mit diesen Kodierungen arbeiten kann. Im Anschluss haben wir dann gesehen, dass die beiden Betrachtungen sich gut ineinander überführen lassen. Zu wissen, dass man mit Turingmaschinen Funktionen berechnen kann, ist aber hilfreich, um sich zu verdeutlichen, dass Turingmaschinen eine formale Abstraktion bzw. ein formales Modell für einen Algorithmus sind

Hier ein paar Fragen zum Berechnen von Funktionen mit TMs.

Die DTM

Posted On 2 Dez 2014
By fgi1
In Uncategorized

Download PDF

Als erstes Modell führen wir die deterministische Turingmaschine ein. Mit dieser wird es möglich sein, alle Sprachen, denen wir bisher begegnet sind, zu akzeptieren und alle Modelle, die wir bisher hatten, zu simulieren. Insbesondere können also alle regulären und alle kontextfreien Sprachen von Turingmaschinen akzeptiert werden.

Definition der DTM

Die deterministische Turingmaschine (kurz DTM oder TM, wenn der Determinismus nicht relevant ist) hat zunächst wie der DFA ein Eingabeband, auf dem zu Anfang ein Eingabewort $w \in \Sigma^*$ steht. Die DTM ist zudem wie der DFA in einem Startzustand $z_0$. Während der DFA nun aber nur einen Lesekopf hat, der ein Symbol vom Eingabeband liest und sich dann ein Feld nach rechts bewegt (während der DFA noch einen Zustandswechsel macht), hat die Turingmaschine einen Lese-Schreib-Kopf (kurz LSK). Mit dem LSK kann die DTM ein Symbol wie der DFA lesen. Dann kann sie an diese Stelle aber ein neues Symbol schreiben und den LSK dann wahlweise nach rechts oder auch nach links bewegen oder die Position des LSK beibehalten.

Damit die DTM genügend Platz für Nebenrechnungen und ähnliches hat, ist das Eingabeband zudem in beide Richtungen unendlich lang. Die Idee dahinter ist, dass ein Mensch, der eine Rechnung auf einem Blatt Papier ausführt, sich auch immer wieder neues Papier holen kann. Man beachte außerdem, dass der Keller des Kellerautomaten im Grunde auch nicht beschränkt war. Auch wenn dies also zunächst nach einer recht umfrangreichen Erweiterung aussieht, ist sie im Grunde genommen ganz naheliegend.

Wir definieren nun die DTM formal. Ähnlich wie beim DFA findet man den LSK nicht in der formalen Definition. Seine Bewegung wird allerdings bei der Überführungsfunktion behandelt. Auch das beidseitig unendliche Band wird in der Definition nicht erwähnt. Man hat es später bei der Definition der Konfigurationsübergänge im Kopf, denn bei einem anderen Band, müsste man hier dann anders definieren.

Definiton 4.1.1 (Deterministische Turingmaschine)

Eine deterministische Turingmaschine (kurz DTM) ist ein $6$-Tupel $A = (Z, \Sigma, \Gamma, \delta, z_0, Z_{end})$ mit

Der endlichen Menge von Zuständen $Z$.
Dem endlichen Alphabet $\Sigma$ von Eingabesymbolen.
Dem endlichen Alphabet $\Gamma$ von Bandsymbolen, wobei $\Gamma \supset \Sigma$ und $\Gamma \cap Z = \emptyset$ gilt.
Der (partiellen) Überführungsfunktion $\delta: (Z \times \Gamma) \rightarrow (\Gamma \times \{L,R,H\} \times Z)$.
Dem Startzustand $z_0 \in Z$.
Der Menge der Endzustände $Z_{end} \subseteq Z$.
Dem Symbol für das leere Feld $\# \in \Gamma \setminus \Sigma$.

Die Turingmaschine ist nach Alan Turing benannt, der sie in den 1930er Jahren einführte. Alan Turing ist eine der bedeutendsten Persönlichkeiten in der Informatik.

Man beachte, dass in der Definition zwischen Eingabe- und Bandsymbolen unterschieden wird. Ein Eingabewort soll nur aus Eingabesymbolen bestehen. Die Turingmaschine kann dann aber z.B. für Nebenrechnungen weitere Symbole benutzen, daher ist $\Gamma \supset \Sigma$. Zudem ist das Symbol für das leere Feld nicht im Eingabealphabet. Mit diesem will man ja gerade ausdrücken, dass auf einem Feld nichts steht. Zuletzt drückt die Überführungsfunktion oben informal beschriebenes formal aus. Abhängig vom Zustand $z$, in dem die DTM ist, und Bandsymbol $x$, das gerade gelesen wird, gibt $\delta(z,x) = (x‘, B, z‘)$ den Nachfolgezustand $z‘$, das Symbol $x‘$ was anstelle von $x$ geschrieben wird und die Bewegung $B \in \{L,R,H\}$ an (links, rechts oder Position halten).

Hinweis (Arbeitsweise der Turingmaschine)

Wir bringen noch einmal auf den Punkt, wie die Turingmaschine arbeitet. Sei $\delta(z,x) = (x',B,z')$, dann

ist die TM im Zustand $z$ und
der LSK gerade über einem Feld, das mit dem Symbol $x$ beschriftet ist.
Nun wird das $x$ durch $x'$ überschrieben und
dann der LSK nach $B \in \{L,R,H\}$ bewegt, wobei
- $L$ nach links bewegen bedeutet,
- $R$ nach rechts bewegen und
- $H$ den LSK an der Stelle halten bedeutet.
Zuletzt wird in den Zustand $z'$ gewechselt.

Wir betonen schon einmal, dass $B = H$ nur bedeutet, dass der LSK nicht bewegt wird. Es heißt insbesondere nicht, dass die TM anhalten würde. Dies wird später, wenn es um entscheidbare Sprachen geht, noch wichtig.

Beispiel einer DTM

Als Beispiel zeigt die Abbildung das Zustandsübergangsdiagramm einer Turingmaschine. Start- und Endzustände werden wie bei DFAs notiert. Die Kantenbeschriftungen sind entsprechend der Überführungsfunktion anders. Die Schleife an $z_0$ entspricht z.B. $\delta(z_0, a) = (X,R,z_0)$ und $\delta(z_0,b) = (b,R,z_0)$.

Wir können nun die Konfiguration einer Turingmaschine definieren und darauf aufbauend dann die Konfigurationsübergänge. Mit letzterem können wir dann, basierend auf der Überführungsfunktion, die Dynamik der Turingmaschine beschreiben. Mit der Konfiguration wollen wir erfassen, in welchem Zustand die DTM ist und wie die aktuelle Bandinschrift aussieht. In der Definition der DTM wurde $\Gamma \cap Z = \emptyset$ gefordert, damit der Zustand nun benutzt werden kann, um die Position des LSK anzugeben. Eine Konfiguration wird ein Wort $uzv$ sein, wobei $uv \in \Gamma^*$ die Bandinschrift angibt und $z$ der Zustand ist, in dem die DTM sich gerade befindet. Unter dem LSK ist dann das erste Symbol von $v$. Zusätzlich wird gefordert, dass $u$ nicht mit $\#$ beginnt und $v$ nicht mit $\#$ endet. $uv$ ist dann also die relevante Bandinschrift und links (von $u$) und rechts (von $v$) stehen nur $\#$.

Definiton 4.1.2 (Konfiguration)

Ein Wort $w \in \Gamma^* \cdot Z \cdot \Gamma^*$ heißt Konfiguration der DTM $A := (Z, \Sigma, \Gamma, \delta, z_0, Z_{end})$. Ist $w = uzv$ mit $z \in Z$ und $u,v \in \Gamma^*$, dann ist

$A$ im Zustand $z$,
die Bandinschrift $uv$ (links/rechts davon nur $\#$) und
das erste Symbol von $v$ unter dem LSK. (Ist $v = \lambda$, so ist $\#$ unter dem LSK. Ist $v \not= \lambda$, so ist $v \in \Gamma^*(\Gamma \setminus \{\#\})$. Ebenso ist im Fall $u \not= \lambda$ dann $u \in (\Gamma \setminus \{\#\})\Gamma^*$.)

Die Menge aller Konfigurationen der TM $M$ ist $\text{KONF}_M$.

Auch wenn dies nicht nötig ist, wird bei $v = \lambda$ oder $u = \lambda$ manchmal links bzw. rechts von $z$ noch ein $\#$ notiert. Diese Konfigurationen wollen wir dann auch erlauben. Allgemein wollen wir links und rechts von $u$ bzw. $v$ beliebig viele $\#$ erlauben. In manchen Konfigurationen bzw. Konfigurationsübergängen erleichtert dies die Arbeitsweise der Turingmaschine zu verstehen, wenn man dies notiert.

Beispiele von Konfigurationen

Mögliche Konfigurationen sind also $zaabb$, $aazbb$ und $aabbz$, aber auch $z \# \# \# aXXb$, $aa \# \# z bbb$, $aa \# \# bbz \#\# cc$ und $aabb\#\# z$. Ferner wollen wir wie gesagt manchmal links oder rechts noch ein $\#$ notieren. So beschreiben z.B. die Konfigurationen $aabbz$ und $aabbz\#$ das gleiche. Bei letzterer erkennt man besser, dass unter dem LSK gerade ein $\#$ ist.

Will man die Konfigurationsübergänge definieren, so wird dies durch die vielen Fälle, in denen links oder rechts etwas gelöscht wird und nicht mehr in der Konfiguration auftritt und durch die Bewegungen erschwert. Eine formale Definition folgt gleich. Das arbeiten mit Konfigurationsübergängen ist aber im Allgemeinen deutlich einfacher. Ist man in einer Konfiguration $uzxv$ mit $u,v \in \Gamma^*$, $x \in \Gamma$ und $z \in Z$, dann betrachtet man $\delta(z,x)$ und ändert die Konfiguration entsprechend (d.h. ersetzt $x$, wechselt den Zustand und positioniert den Zustand in der Konfiguration neu). Dabei achtet man dann noch darauf, dass links und rechts nichts unnötiges stehen bleibt und schon erreicht man informal genau das, was formal ausgedrückt recht kompliziert ist.

Definiton 4.1.3 (Schrittrelation einer DTM)

Sei $A$ eine DTM. Die Schrittrelation $\vdash_A \subseteq \text{KONF}_A \times \text{KONF}_A$ ist definiert durch: $w \vdash_A w‘$ gilt gdw. 1, 2, 3 oder 4 unten gilt.

Es ist $u,v,w \in \Gamma^*$, $x,y,z \in \Gamma$, $p,q \in Z$.

$w = uypxv$ und
$$ w‘ = \left\{ \begin{array}{l}
uqyzv, \mbox{ falls } (v \neq \lambda \mbox{ oder } z \neq \#)
\mbox{ und } \delta(p, x) = (z, L, q) \\
uqy, \mbox{ falls } v = \lambda, y \neq \#
\mbox{ und } \delta(p, x) = (\#, L, q) \\
uq, \mbox{ falls } v = \lambda, y = \#
\mbox{ und } \delta(p, x) = (\#, L, q) \\
uyzqv, \mbox{ falls } \delta(p, x) = (z, R, q) \\
uyqzv \mbox{ falls } (v \neq \lambda \mbox{ oder } z \neq \#) \mbox{ und } \delta(p, x) = (z, H, q) \\
uyq \mbox{ falls } v = \lambda \mbox{ und } \delta(p, x) = (\#, H, q)
\end{array} \right. $$
$w = uyp$ und
$$ w‘ = \left\{ \begin{array}{l}
uqyz, \mbox{ falls } z \neq \# \mbox{ und } \delta(p, \#) = (z, L, q) \\
uqy, \mbox{ falls } y \neq \# \mbox{ und } d(p, \#) = (\#, L, q) \\
uq, \mbox{ falls } y = \# \mbox{ und } \delta(p, \#) = (\#, L, q) \\
uyzq, \mbox{ falls } \delta(p, \#) = (z, R, q) \\
uyqz, \mbox{ falls } z \neq \# \mbox{ und } \delta(p, \#) = (z, H, q) \\
uyq, \mbox{ falls } \delta(p, \#) = (\#, H, q)
\end{array} \right. $$
$w = pxv$ und
$$ w‘ = \left\{ \begin{array}{l}
q\#zv, \mbox{ falls } \delta(p, x) = (z, L, q) \\
zqv, \mbox{ falls } \delta(p, x) = (z, R, q) \\
qzv, \mbox{ falls } \delta(p, x) = (z, H, q)
\end{array} \right. $$
$w = p$ und
$$ w‘ = \left\{ \begin{array}{l}
q\#z, \mbox{ falls } \delta(p, \#) = (z, L, q) \\
zq, \mbox{ falls } \delta(p, \#) = (z, R, q) \\
qz, \mbox{ falls } z \neq \# \mbox{ und } \delta(p, \#) = (z, H, q) \\
q, \mbox{ falls } \delta(p, \#) = (\#, H, q)
\end{array} \right. $$

Die Definition ist wie gesagt recht technisch, um etwas eigentlich ganz einfaches vollständig auszudrücken. Ein kleines Beispiel verdeutlicht wie einfach das Arbeiten mit der Schrittrelation ist.

Beispiel zur Schrittrelation

Betrachten wir die abgebildete DTM. Sei das Eingabewort $w = aab$. Die DTM startet also in der Konfiguration $z_0aab$.

Als Konfigurationsübergänge haben wir dann durch die Schrittrelation $$ z_0 aab \vdash Xz_0ab \vdash XXz_0b \vdash XXbz_0\# \vdash XXz_1b \vdash XXbz_2\# $$ An beiden Stelle, wo dies auftritt, wäre das $\#$ ganz rechts nicht nötig (und nach Definition auch nicht vorhanden). Es erleichtert aber insbesondere im ersten Fall zu erkennen, was die DTM als nächstes tun kann.

Wie bei unseren bisherigen Automatenmodellen führen wir wieder den Begriff der Rechnung und der Erfolgsrechnung ein und definieren dann, was die von einer DTM akzeptierte Sprache ist.

Definiton 4.1.4 (Rechnung einer DTM)

Sei $A = (Z, \Sigma, \Gamma, \delta, z_0, Z_{end})$ eine DTM.

Mit $\vdash_A^*$ wird die reflexive, transitive Hülle von $\vdash_A$ bezeichnet. Der Index $A$ kann auch weggelassen werden, wenn klar ist, welche DTM gemeint ist.
Eine Folge $k_1 \vdash k_2 \vdash \ldots \vdash k_i \vdash \ldots$ heißt Rechnung der DTM $A$.
Eine endliche Rechnung $k_1 \vdash k_2 \vdash \ldots \vdash k_n$ heißt Erfolgsrechnung, wenn $k_1 \in \{z_0\} \cdot \Sigma^*$ und $k_n \in \Gamma^* \cdot Z_{end} \cdot \Gamma^*$ gilt.
Die von $A$ akzeptierte Sprache ist $$ L(A) := \{ w \in \Sigma^* \mid \exists u,v \in \Gamma^* \ \exists z_e \in Z_{end}:\ z_0w \vdash^* uz_ev \}. $$

Die akzeptierte Sprache ist anders als wir dies bisher gewohnt sind. Man beachte, dass Worte aus $w \in \Sigma^*$ akzeptiert werden (das waren wir noch gewohnt) und dass dies geschieht, sobald die DTM bei der Rechnung einen Endzustand besucht. Es ist also anders als sonst nicht nötig, dass die Rechnung im Endzustand endet! Man könnte zwar alle Kanten aus einem Endzustand entfernen, so dass die Rechnung hier stets endet, aber dies ist nicht gefordert. Außerdem muss die DTM sich nicht das ganze Eingabewort angesehen haben, um zu akzeptieren. Auch dies ist anders als bei z.B. DFAs. Das Eingabewort muss nicht einmal mehr auf dem Band sein. Der Bandinhalt kann im Gegenteil nun ganz anders aussehen. Wichtig ist nur, dass die DTM einen Endzustand erreicht. Warum diese Definition? Die Turingmaschine wurde als Modell des Berechenbaren eingeführt und dient also als Modell für einen Algorithmus. Wenn man z.B. in einem Algorithmus einen kürzesten Pfad in einem Graphen bestimmt, dann muss man sich dazu nicht zwingend den ganzen Graphen ansehen. Auch wenn man wissen will, ob in einem Wort über $\{a,b\}$ mindestens zwei $b$ vorkommen, kann man aufhören, sobald man das zweite gesehen hat. Daher ist es sinnvoll bei der DTM die Definition so zu machen, dass sie nur in einen Endzustand gelangen muss. Das nun ein ganz anderes Wort auf dem Band stehen kann, liegt daran, dass hier u.U. auch viele Zwischenrechnungen und ähnliches notiert sein können.

Hinweis zum Akzeptieren

Wir betonen noch einmal: die DTM startet in der Konfiguration $z_0 w$ mit $w \in \Sigma^*$ ganz so wie auch bei einem DFA. Dann macht sie Konfigurationsübergänge entsprechend der Übergangsfunktion. Gelangt sie dabei in eine Konfiguration $u z_e v$ in der $z_e$ ein Endzustand ist, so wird das ursprüngliche Eingabewort $w$ akzeptiert (nicht etwas $uv$). Was aus $w$ wurde ist egal, wie die aktuelle Bandinschrift aussieht ist egal und ob sie noch weiterrechnen könnte ist auch egal. Erreicht sie eine Konfiguration $u z_e v$, in der $z_e$ ein Endzustand ist, wird das ursprüngliche Eingabewort $w$ akzeptiert.

Beispiele

Wir wollen noch zwei Beispiele betrachten. Sei zunächst abermals die folgende DTM gegeben, die wir mit $A$ bezeichnen wollen. Welche Sprache $L \subseteq \{a,b\}^*$ akzeptiert diese TM?.

In $z_0$ wird zunächst über die $a$ und $b$ des Wortes gelesen. Dabei wird der LSK immer weiter nach rechts bewegt. Aus einem $a$ wird ein $X$, die $b$ werden belassen. Man gelangt so von einer Konfiguration $z_0 w$ in eine Konfiguration $w' z_0$, wobei $w'$ aus $w$ hervorgeht, indem jedes $a$ durch $X$ ersetzt wird. Dann wird der Übergang von $z_0$ nach $z_1$ gemacht und der LSK nach links bewegt. Er befindet sich nun auf dem letzten Symbol von $w'$. In $z_1$ ist nun nur eine Kante. Diese kann genutzt werden, wenn das letzte Symbol von $w'$ gerade ein $b$ ist. Ist dies der Fall, so wird in den einzigen Endzustand $z_2$ gewechselt und das Eingabewort akzeptiert. $w$ wird also genau dann akzeptiert, wenn $w'$ auf $b$ endet, da $w'$ nur auf $b$ endet, wenn auch $w$ dies tut (die $b$ wurden ja nicht ersetzt), akzeptiert die DTM also genau die Worte, die auf $b$ enden. Damit haben wir $$ L(A) = \{w \in \{a,b\}^* \mid w \text{ endet auf $b$}\}. $$

Betrachten wir als nächstes die folgende abgebildete sehr kleine DTM $B$. Welche Sprache $L \subseteq \{a,b\}^*$ akzeptiert diese TM?

Offensichtlich kann sie keine $a$ lesen. Ein $b$ überführt die DTM aber nach $z_1$. Beginnt ein Eingabewort also mit $a$, so blockiert $B$, beginnt ein Eingabewort hingegen mit $b$, so wird nach $z_1$ gewechselt und dort akzeptiert. Man beachte noch einmal, dass es bei Turingmaschinen nicht wichtig ist, das Eingabewort zu Ende zu lesen. Hier haben wir also $$ L(B) = \{w \in \{a,b\}^* \mid w \text{ beginnt mit $b$}\}.$$

Wiederholung

Wir fassen das bisherige zusammen. Wir haben die deterministische Turingmaschine (DTM) eingeführt, die recht ähnlich zum DFA ist, aber auf dem Eingabeband nicht nur lesen, sondern auch schreiben kann und die zudem mit ihrem Lese-Schreib-Kopf (LSK) nach links und rechts gehen kann. Das Eingabeband ist zudem in beide Richtungen unendlich lang.

Um die Arbeitsweise exakt zu definieren, haben wir wieder Konfigurationen und die Schrittrelation eingeführt. Darauf aufbauend haben wir dann die Begriffe Rechnung und Erfolgsrechnung eingeführt und die akzeptierte Sprache definiert. Die DTM akzeptiert ein Wort dann, wenn sie einen Endzustand erreicht. Wie die aktuelle Konfiguration dann genau aussieht und ob sie das Eingabewort zu Ende gelesen hat, ist anders als bei DFAs nicht relevant.

Hier ein paar Fragen zu Turingmaschinen.

Turingmaschinen

Posted On 1 Dez 2014
By fgi1
In Uncategorized

Download PDF

Nachdem wir in den letzten Kapiteln verschiedene Automatenmodelle und Grammatiken eingeführt bzw. gestreift haben, wollen wir in diesem Kapitel ein weiteres, sehr mächtiges Automatenmodell einführen: die Turingmaschine. Die Turingmaschine ähnelt zunächst sehr einem DFA. Wir erlauben der Turingmaschine aber zusätzlich auf dem Eingabeband nicht nur nach rechts, sondern auch nach links zu gehen und wir erlauben ihr nicht nur ein Symbol zu lesen, sondern auch ein Symbol auf das Band zu schreiben. Diese Änderung führen zu einem sehr mächtigen Modell. Tatsächlich gilt die Turingmaschine als abstraktes Modell dessen, was von jeder Maschine oder jedem Menschen berechnet werden kann, d.h. was immer wir oder eine von uns konstruierte Maschine berechnen kann, das kann auch die Turingmaschine berechnen. Wir werden dieser Aussage später als Church-Turing-These wieder begegnen. Diese These ist so formuliert nicht beweisbar, denn wer weiß schon mit Sicherheit, was wir in der Zukunft konstruieren? Sie hat sich aber als erstaunlich robust erwiesen, denn auch alle neueren Rechnermodelle wie bspw. Parallelrechner lassen sich von Turingmaschinen simulieren. Besonders interessant ist auch der Umkehrschluss: was von einer Turingmaschine nicht berechnet werden kann, das kann auch kein Mensch oder keine von ihm erbaute Maschine berechnen.

In den folgenden Abschnitten wollen wir die Turingmaschine einführen, Varianten von ihr wie z.B. eine nichtdeterministische Turingmaschine betrachten und dann die wichtigen Sprachfamilien der entscheidbaren und der aufzählbaren Sprachen einführen. Insb. die entscheidbaren Sprachen spielen bei Algorithmen eine wichtige Rolle. Wir werden dann zeigen, dass es auch unentscheidbare Probleme gibt, d.h. Probleme, für die es keinen Algorithmus geben kann, der sie löst. Ein Resultat, das von besonderer Bedeutung für die Informatik ist, da es uns unsere Grenzen mit dem Computer aufzeigt – und wir werden sehen, dass diese Grenze schon überraschend früh kommt.

Blog Archives

Definiton 5.2.1 (Die Klassen P und NP)

Satz 5.2.2

Beweis

Definiton 5.2.3 (Verifikationsalgorithmus)

Definiton 5.2.4 (NP (alternative Definition)

Satz 5.2.5

Beweis

Definiton 5.2.6 (Typische NP-Probleme)

Definiton 5.1.1 (Zeit- und Platzkomplexität einer deterministischen Turingmaschine)

Definiton 5.1.2 (Zeit- und Platzkomplexität einer nichtdeterministischen Turingmaschine)

Komplexitätsklassen

Definiton 5.1.3 (Komplexitätsklasse)

Definiton 5.1.4 (P, NP, PSPACE und NPSPACE)

Satz 5.1.5

Quiz-Zusammenfassung

Informationen

Ergebnis

Kategorien

1. Frage

2. Frage

3. Frage

Ein unentscheidbares Problem

Satz 4.4.1

Beweise

Weitere unentscheidbare Probleme

Satz 4.4.2

Beweise

Satz 4.4.3

Beweise

Nicht mal mehr aufzählbar

Satz 4.4.4

Beweise

Quiz-Zusammenfassung

Informationen

Ergebnis

Kategorien

1. Frage

2. Frage

3. Frage

4. Frage

Die Sprachfamilien RE und REC

Definiton 4.3.1 (Die aufzählbaren Sprachen)

Definiton 4.3.2 (Die entscheidbaren Sprachen)

Satz 4.3.3

Satz 4.3.4

Beispiele entscheidbarer Sprachen

Satz 4.3.5

Beweise

Satz 4.3.6

Beweise

Satz 4.3.7

Beweise

Satz 4.3.8

Beweise

Satz 4.3.9

Beweise

Beispiele aufzählbarer Sprachen

Satz 4.3.10

Beweise

Satz 4.3.11

Abschlusseigenshaften

Satz 4.3.12

Beweise

Satz 4.3.13

Beweise

Quiz-Zusammenfassung

Informationen

Ergebnis

Kategorien

1. Frage

2. Frage

3. Frage

4. Frage

Definiton 4.2.1

Nutzung verschiedener Bänder

Definiton 4.2.2

Satz 4.2.3

Beweisidee

Definiton 4.2.4 (k-Band off-line Turingmaschine)