2-turingmaschinen-berechenbarkeit-komplexitaetsklassen.tex

%!TEX root = 0-main.tex

% Author: Philipp Moers <soziflip@gmail.com> 



\datum{12.10.15}

\chapter{Turingmaschinen, Berechenbarkeit und Komplexität} % (fold)
\label{cha:turingmaschinen_berechenbarkeit_und_komplexitaet}



\section{Turingmaschinen}


\begin{definition}
        
    Eine \definiere{Turingmaschine} $T$ mit $k$ Bändern ist ein 5-Tupel
    $$ T = (Q, \Sigma, I, q_0, F) $$
    \begin{itemize}
        \item $Q$ ist eine endliche Menge von Zuständen
        \item $\Sigma$ ist eine endliche Menge von Bandsymbolen, $\square \in \Sigma$
        \item $I$ ist eine Menge von Quintupeln der Form $(q, s, s', m, q')$ mit $q, q' \in Q$ und $s, s' \in \Sigma^k$ und $m \in \{ L, R, S \}^k$ 
        \item $q_0 \in Q$ Startzustand
        \item $F \subseteq Q$ Endzustände
    \end{itemize}

    $\square$ ist das Leerzeichen oder \definiere{Blanksymbol}.

    $T$ heißt \definiere{deterministisch} genau dann, wenn für jedes $q \in Q$ und $s \in \Sigma^k$ genau ein Quintupel der Form $(q, s, \_, \_, \_) \in I$ existiert. Sonst heißt $T$ \definiere{nichtdeterministisch}.

    Eine Turingmaschine heißt \definiere{Akzeptormaschine} genau dann, wenn zwei Zustände $q_A, q_R \in F$ speziell markiert sind. $q_A$ signalisiert Akzeptanz, $q_R$ signalisiert Verwerfen der Eingabe.

    Eine Turingmaschine heißt \definiere{Transducermaschine} genau dann, wenn ein zusätzliches Band ausgezeichnet ist (das Ausgabeband).

\end{definition}



\begin{beispiel}
\label{nullenundeinsen}

    Akzeptormaschine $T$ für Sprache $L = \{ 0^n 1^n | n \geq 0 \}$ wobei $\Sigma= \{0,1\}, Q = \{q_0, \dots q_4 \}$

    $T$ wird deterministisch sein. $T = (Q, \Sigma, I, q_0, F), q_A = q_1, q_R = q_2, F = \{q_1, q_2\}, k=2$

    \vspace{2pt}
    \begin{tabular}{|c|c|c|c|c|c|c|c|}\hline
    \rowcolor{grau} $q$   & $s_1$     & $s_2$     & $s_1'$    & $s_2'$    & $m_1$ & $m_2$ & $q'$    \\\hline
                    $q_0$ & $\square$ & $\square$ & $\square$ & $\square$ & $S$   & $S$   & $q_1$   \\\hline
                    $q_0$ & $0$       & $\square$ & $0$       & $0$       & $R$   & $R$   & $q_3$   \\\hline
                    $q_0$ & $1$       & $\square$ & $1$       & $\square$ & $S$   & $S$   & $q_2$   \\\hline
                    $q_3$ & $\square$ & $\square$ & $\_$      & $\_$      & $\_$  & $\_$  & $q_2$   \\\hline
                    $q_3$ & $0$       & $\square$ & $0$       & $0$       & $R$   & $R$   & $q_3$   \\\hline
                    $q_3$ & $1$       & $\square$ & $1$       & $\square$ & $S$   & $L$   & $q_4$   \\\hline
                    $q_4$ & $0$       & $0$       & $\_$      & $\_$      & $\_$  & $\_$  & $q_2$   \\\hline
                    $q_4$ & $1$       & $0$       & $1$       & $0$       & $R$   & $L$   & $q_4$   \\\hline
                    $q_4$ & $0$       & $\square$ & $\square$ & $\square$ & $S$   & $S$   & $q_1$   \\\hline
                    $\_$  & $\_$      & $\_$      & $\_$      & $\_$      & $\_$  & $\_$  & $q_2$   \\\hline
    \end{tabular}

\end{beispiel}


Die \definiere{globale Konfiguration} (oder der \definiere{Zustand}) einer Turingmaschine beinhaltet die Beschriftung aller Bänder, den internen Zustand ($\in Q$) und die Positionen aller $k$ Lese-/Schreibköpfe. Globale Konfigurationen können als endliche Wörter über einem geeigneten Alphabet (z.\,B. $\{0,1\}$) codiert werden.


Eine Turingmaschine \definiere{akzeptiert} eine Eingabe genau dann, wenn eine Berechnungsfolge ausgehend von dieser Eingabe existiert und in einem Zustand aus $F$ endet.

Eine Turingmaschine \definiere{akzeptiert} eine Sprache $L \subseteq \left( \Sigma \setminus \{\square\} \right)^\ast$ falls gilt: 
$$ \text{Die Turingmaschine akzeptiert } w \Leftrightarrow w \in L $$

Eine Turingmaschine \definiere{entscheidet} eine Sprache $L \subseteq \left( \Sigma \setminus \{\square\} \right)^\ast$ genau dann, wenn sie sie akzeptiert und eine/die Berechnung in $q_A$ endet.













\datum{15.10.15}


Zu \definiere{Mehrband-Turingmaschinen}:

Bisher waren die Bänder beidseitig unendlich. Ab jetzt und im Buch sind sie nur noch einseitig unendlich.



\begin{satz}
    Eine Mehrband-Turingmaschine mit $k$ Bändern kann durch eine Einband-Turingmaschine simuliert werden.

    Dies benötigt quadratischen Mehraufwand.
\end{satz}

\begin{beweis}
    Die Beweisidee nutzt für das alte Alphabet $\Sigma$ das neue Alphabet $\Sigma^k \times \{0,1\}^k$, das die Zeichen auf den Bändern und, ob der Lese-/Schreibkopf an dieser Position steht, speichert.
\end{beweis}



\begin{definition}
    Eine \definiere{universelle Turingmaschine} erhält als Eingabe $(M, x)$, wobei $M$ die Beschreibung einer Turingmaschine in geeignetem Binärformat und $x$ die Eingabe für $M$ ist.
    Sie berechnet dann die Ausführung von $M$ auf $x$.
\end{definition}




\section{Halteproblem}


\begin{definition}
    Gegeben Turingmaschine und Eingabe $(M, x)$. Das Problem, zu entscheiden, ob $M$ angewendet auf $x$ hält oder nicht, heißt \definiere{Halteproblem}.
\end{definition}

\begin{satz}
    Das Halteproblem ist unentscheidbar.
\end{satz}

\begin{beweis}
    Angenommen, es gäbe eine Turingmaschine $M_{HALT}$, die das Halteproblem entscheidet.

    Dann könnten wir auch eine neue Turingmaschine $M_D$ konstruieren:\\
    Simuliere Eingabe $M$ auf $M$ selbst und schaue, ob sie hält. Falls ja, dann gehe in Endlosschleife. Falls nicht, halte an.

    Für $M = M_D$ ergibt sich nun ein Widerspruch: Falls sie hält, hält sie nicht. Falls sie nicht hält, hält sie.
\end{beweis}




\section{Rechenzeit}


\begin{definition}
    Die \definiere{Rechenzeit} definiert man wie folgt:

    Gegeben eine Turingmaschine $M$ und Eingabe $x$. 

    $TIME_M(x)$ ist die Dauer (Anzahl der Schritte) der Berechnung von $M$ auf $x$.
\end{definition}

% Im Beispiel \ref{nullenundeinsen} bla
Im Beispiel der Maschine für $L = \{ 0^n 1^n | n \geq 0 \}$ ist $TIME_M(x) = |x| $ (Länge des Strings).




\begin{satz}
    Das \definiere{Speedup-Theorem} besagt, dass zu jeder Turingmaschine $M$ eine äquivalente Turingmaschine $M'$ konstruiert werden kann, sodass

    $$ TIME_{M'}(x) \leq \frac{1}{k} * TIME_M(x) $$

    wobei $k \in \N \setminus \{0\}$ fest gewählt ist.
\end{satz}

Zum Beispiel ist bei $k = 7$ die neue Turingmaschine siebenmal so schnell.

\begin{beweis}
    Gegeben $M$ mit Alphabet $\Sigma$.

    Dann wird $M'$ mit Alphabet $\Sigma^k$ konstruiert. Ein Symbol von $M'$ repräsentiert $k$ aufeinanderfolgende Symbole von $M$, d.h. $M'$ kann $k$ Schritte von $M$ ein einem einzigen ausführen.
\end{beweis}

\textbf{Anmerkung:}

Die Schritte werden in der Praxis also schon aufwändiger, die definierte Metrik $TIME$ erfasst das nur nicht. No Magic here.



\begin{definition}
    Sei $f: \N \rightarrow \N$. 

    Dann definieren wir $DTIME(f)$ als Menge aller Entscheidungsprobleme (oder Berechnungsprobleme) $A$, zu denen eine \underline{deterministische} Turingmaschine $M$ existiert, sodass $M$ $A$ entscheidet und die Rechenzeit in $\bigO(f(n))$ liegt.

    $$ DTIME(f) = \{  
        A 
        \ |\ 
        \exists M: 
            M \text{ entscheidet } A
            \text{ und }
            \forall x \in \Sigma^\ast: TIME_M(x) = \bigO(f(|x))
    \}
    $$
\end{definition}

\begin{satz}
    Matrixmultiplikation liegt in $\bigO(n^3)$, also in $DTIME(\sqrt{n}^3)$, wenn die Länge der Matrix auf dem Band $n$ ist.
    Sie liegt sogar in $\bigO(n^{2.78})$
\end{satz}

Offen ist die Frage, ob sie in $DTIME(\sqrt{n}^2)$ liegt.



\section{Komplexitätsklassen}


\begin{definition}
    Eine Menge der Form $DTIME(f(n))$ heißt \definiere{deterministische Zeitkomplexitätsklasse}.
    Analog heißt $NTIME(f(n))$ für nichtdeterministische Turingmaschinen \definiere{nichtdeterministische Zeitkomplexitätsklasse}.
\end{definition}


Wir betrachten zu gegebener Funktion $f: \N \rightarrow \N$ durch Turingmaschine $M$ folgenden Algorithmus:

Rechne $M$ auf Eingabe $M$ selbst für $f(M)$ Schritte. Falls $M$ sich bis dahin akzeptiert, verwerfe die Eingabe. Falls sie sich verwirft oder bis dahin nicht gehalten hat, akzeptiere die Eingabe.

Das durch diesen Algorithmus beschriebene Problem 
$$K_f = \{ M \ |\ M \text{ akzeptiert sich selbst nicht in höchstens } f(|M|) \text{ Schritten.} \}$$ 
ist ``offensichtlich'' entscheidbar. Die Rechenzeit für diese Entscheidung muss aber im allgemeinen $f(|M|)$ übersteigen.
    
Wäre $M_f$ eine Turingmaschine, die $K_f$ entscheidet und außerdem $TIME_{M_f} \leq f(|x|)$ für alle $x$, dann führt die Anwendung von $M_f$ auf $M_f$ selbst zum Widerspruch (wie beim Halteproblem).

$f$ muss dazu selbst in Zeit $\bigO(f(n))$ berechenbar und monoton steigend sein. Man nennt $f$ dann \definiere{zeitkonstruierbar}.

Durch geschickte Ausnutzung dieses Arguments erhält man den \definiere{Zeit-Hierarchie-Satz}:

\begin{satz}
    Falls $f: \N \rightarrow \N$ zeitkonstruierbar ist, dann gilt:
    $$ DTIME(f(n)) \subset DTIME(f(n)*\log^2(f(n))) $$
    wobei $\subset$ eine echte Teilmengenbeziehung bezeichnet.
\end{satz}

\textbf{Anmerkung:}

``Vernünftige'' Funktionen wie $2^n$, $\log(n)$, $\sqrt{n}$ etc. sind zeitkonstruierbar.




\begin{satz}
    Nach Borodin und Trakhtenbrot gilt das \definiere{Gap-Theorem}:

    Für eine totale, berechenbare Funktion $g: \N \rightarrow \N$ mit $g(n) \geq n$ gibt es immer eine totale, berechenbare Funktion $f: \N \rightarrow \N$, sodass gilt:
    $$ DTIME(f) = DTIME (g \circ f) $$

    Es gibt also in der Hierarchie der Komplexitätsklassen beliebig große Lücken.
\end{satz}


\begin{definition}
    \definiere{Wichtige Komplexitätsklassen:} 
    $$ \ComplexityClassP = \bigcup_{k \geq 1} DTIME(n^k) $$
    $$ \ComplexityClassE = \bigcup_{k \geq 1} DTIME(2^{kn}) $$
    $$ \ComplexityClassEXP = \bigcup_{k \geq 1} DTIME(2^{n^k}) $$
\end{definition}

Nach dem \definiere{Zeit-Hierarchie-Satz} gilt:
$$ \ComplexityClassP \subset \ComplexityClassE \subset \ComplexityClassEXP $$













\datum{19.10.15}

\begin{definition}

    \definiere{Nichtdeterministische Zeitkomplexität}
    Sei $T$ eine nichtdeterministische Turingmaschine. 

    Für $x \in \Sigma$ ist $NTIME_T(x)$
    \begin{enumerate}
        \item definiert genau dann, wenn alle Berechnungen von $T$ auf $x$ halten
        \item Falls definiert und $x \in L(T)$ (d.h. es gibt eine akzeptierende Berechnung von $T$ auf $x$) definiert als Länge der kürzesten akzeptierenden Berechnungen von $T$ auf $x$.
        \item Falls überhaupt definiert $x \notin L(T)$ so ist $NTIME_{(x)}$ die Länge der kürzesten Berechnung.
    \end{enumerate}

\end{definition}


\begin{definition}
    % TODO esox ? was ist das?
    % TODO verstehen
    Nichtdeterministische Komplexitätsklassen 
    $$ NTIME(f(n)) = \{ L | \exists T \text{ mit } L(T)=L \text{ und } NTIME_T(x) = \bigO(f(|x|)) \} $$

    Es gibt einen nichtdeterministischen Zeithierachiesatz.

    % P=U DTIME(n^k), NP = U NTIME(n^k)
    % k>=1                k>=1

    % E = U DTIME(2^kn), NE= U NTIME(2^KN)
    % k>=1               k>=1

    % EXP = DTIME(2^n^k), NEXP= U NTIME(2^N^k)
    % k>=1                k>=1

    $$ \ComplexityClassNP   = \bigcup_{k \geq 1} NTIME(n^k) $$
    $$ \ComplexityClassNE   = \bigcup_{k \geq 1} NTIME(2^{kn}) $$
    $$ \ComplexityClassNEXP = \bigcup_{k \geq 1} NTIME(2^{n^k}) $$

\end{definition}


Nichtdeterminismus kann durch erschöpfende Suche deterministsch simuliert werden.
z.B. $\ComplexityClassNP \subseteq \ComplexityClassEXP$


Allgemein:
$$NTIME(f(n)) \subseteq DTIME(2^{\bigO(f(n)})$$

(zeitkonstruierbar)
% ........\ --- Zeitkonstruierbar


\section{polynomielle Verifizierbarkeit}


\begin{definition}

    Charakterisierung von $\ComplexityClassNP$ durch \definiere{polynomielle Verifizierbarkeit} $PV$.

    \begin{align*}
        L \subseteq \Sigma^{\ast} . & L \in PV \text{ genau dann, wenn }\\
                                  & \exists V \in \ComplexityClassP ~~~\exists \text{ Polynom } p : \\
                                  & L = \{ x ~|~ \exists y \in \{0,1\}^\ast : |y| \leq p(|x|) \land
                                    x\#y \in V \}
    \end{align*}
    wobei $\# \notin \Sigma$

\end{definition}


\begin{satz}
    $$ \ComplexityClassNP = PV $$
\end{satz}
\begin{beweis}
    ``$\subseteq$'':

    $L \in \ComplexityClassNP$ . Sei $T$ eine nichtdeterministische Turingmaschine für $L$ mit Laufzeit $p(n)$.

    $$ L' = \{(x,y) | y \text{ codiert eine akzeptierende Berechnung von } T \text{ auf } x \} $$

    \begin{enumerate}
        % TODO . (x,y,) ??? dafuq clemens
        \item $x \in L \Leftrightarrow  \exists y: |y| \leq (p(|x|))^2 . (x,y,) \in L'$
        \item $L' \in \ComplexityClassP$
    \end{enumerate}


    ``$\supseteq$'':

     Gegeben $L, L' \in P$. 

     Eine nichtdeterministische Turingmaschine $T$ für $L$ rät zunächst $y$ und prüft dann $(x,y) \in L'$
\end{beweis}
  

$\ComplexityClassEXP$ im Gegensartz zu $\ComplexityClassNP$ bzw. $PV$ umfasst auch Probleme mit exponentiell großen Lösungen bzw solchen wo die Verifikation einer Lösung einen exponentiellen Aufwand macht.






% chapter turingmaschinen_berechenbarkeit_und_komplexitaet (end)