\defineUnit{tmdefinition}{%
\begin{frame}
    \frametitle{Turingmaschinen}
    \setbeamercovered{dynamic}

    \begin{definition}[Turingmaschine]
        Eine deterministische \structure{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
        \begin{itemize}
            \item endlichen Menge von \structure{Zuständen} $Q$
            \item endlichen \structure{Eingabealphabet} $\Sigma$
            \item endlichen \structure{Bandalphabet} $\Gamma$ mit $\Sigma \subset \Gamma$
            \item \structure{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$
            \item \structure{Startzustand} $q_0 \in Q$
            \item \structure{Leerzeichen} $\square \in \Gamma \setminus \Sigma$
            \item Menge von \structure{Endzuständen} $F \subseteq Q$
        \end{itemize}
    \end{definition}
\end{frame}
}

\defineUnit{tmvisualisierung}{%
\begin{frame}
    \frametitle{Turingmaschinen}
    \setbeamercovered{dynamic}

    \begin{definition}[Turingmaschine]
        Eine deterministische \structure{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
        \begin{itemize}
            \item \structure{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$
        \end{itemize}
    \end{definition}

    \vfill

    \begin{center}
        \begin{tikzpicture}
            % Tape
            \begin{scope}[start chain, node distance=0]
                \node[on chain] {\ldots};
                \node[tape] {$\square$};
                \node[tape] (l) {$\square$};
                \node[tape] {$0$};
                \node[tape] {$1$};
                \node<1>[tape, active] (a){$0$};
                \node<2>[tape] (a){$1$};
                \node<1>[tape] (b){$0$};
                \node<2>[tape, active] (b){$0$};
                \node[tape] {$\square$};
                \node[on chain] {\ldots};
            \end{scope}

            % Head
            \node<1> [head,yshift=-4mm] at (a.south) (head) {$q_0$};
            \node<2> [head,yshift=-4mm] at (b.south) (head) {$q_1$};

            % Machine
            \node[machine, below=1.5cm of l] (machine) {Programm};
            \draw[every edge] (machine) .. controls (3.5, -2) .. (head.south);

            % Example-Transition
            \node[yshift=5mm] at (current bounding box.north) {$\delta(q_0, 0) = (q_1, 1, R)$};
        \end{tikzpicture}
    \end{center}
\end{frame}
}

\defineUnit{tmkonfiguration}{%
\begin{frame}
    \frametitle{Turingmaschinen}
    \setbeamercovered{dynamic}

    \begin{definition}[Konfiguration]
        Eine \structure{Konfiguration} ist ein Tripel $(\alpha, q, \beta) \in \Gamma^* \times Q \times \Gamma^*$. \\
        Dies modelliert eine TM mit:
        \begin{itemize}
            \item \structure{Bandinhalt} $\ldots\square\alpha\beta\square\ldots$
            \item \structure{Zustand} $q$
            \item Kopf auf dem \structure{ersten Zeichen} von $\beta\square$
        \end{itemize}
        Die \structure{Startkonfiguration} bei Eingabe $w \in \Sigma^*$ ist $(\epsilon, q_0, w)$.
    \end{definition}

    \vfill

    \only<1> {
        \begin{center}
            \begin{tikzpicture}
            % Tape
                \begin{scope}[start chain, node distance=0]
                    \node[on chain] {\ldots};
                    \node[tape] {$\square$};
                    \node[tape] (l) {$\square$};
                    \node[tape] {$0$};
                    \node[tape] {$1$};
                    \node[tape] (a){$1$};
                    \node[tape, active] (b){$0$};
                    \node[tape] {$\square$};
                    \node[on chain] {\ldots};
                \end{scope}

            % Head
                \node [head,yshift=-4mm] at (b.south) (head) {$q_1$};

            % Machine
                \node[below=1.5cm of l] (machine) {};
                \draw[every edge, dashed] (machine) .. controls (3.5, -2) .. (head.south);

            % Example-Transition
                \node[yshift=5mm] at (current bounding box.north) {$(011,q_1,0)$};
            \end{tikzpicture}
        \end{center}
    }

    \only<2> {
        \begin{definition}[Akzeptanz]
            Eine TM $M$ \structure{akzeptiert} die Sprache
            \[ L(M) = \left\{ w \in \Sigma^* \mid \exists \alert{f \in F}, \alpha, \beta \in \Gamma^* . (\epsilon, q_0, w) \rightarrow_M^* (\alpha, \alert{f}, \beta) \right\} \]
        \end{definition}
    }
\end{frame}
}

\defineUnit{ndtm}{%
\begin{frame}
    \frametitle{Nichtdeterministische TM}
    \setbeamercovered{dynamic}

    \begin{definition}[Nichtdeterministische Turingmaschine]
        Eine \structure{nichtdeterministische} Turingmaschine (TM) ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
        \begin{itemize}
            \item \ldots
            \item \structure{Übergangsfunktion} $\delta : Q \times \Gamma \to \mathcal{P} \left( Q \times \Gamma \times \left\{ L, R, N \right\} \right)$
            \item \ldots
        \end{itemize}
    \end{definition}

    \vfill

    \begin{theorem}
        Zu jeder nichtdeterministischen TM $N$ gibt es eine deterministische TM $M$ mit \alert{$L(N) = L(M)$}.
    \end{theorem}
\end{frame}
}

\defineUnit{lba}{%
\begin{frame}
    \frametitle{Linear Beschränkte Automaten}

    \begin{definition}[Linear Beschränkte Automat]
        Eine TM heißt \structure{linear beschränkt (LBA)}, wenn sie den Bereich des Bandes, auf dem das Eingabewort steht, niemals verlässt.
    \end{definition}

    \vfill

    \begin{theorem}[]
        Die \structure{linear beschränkten NDTMs} akzeptieren genau die Klasse der \alert{kontextsensitiven Sprachen (Typ 1)}.
    \end{theorem}
\end{frame}
}

\defineUnit{queueautomaten}{%
\begin{frame}
    \frametitle{Queue-Automaten}

    \begin{definition}[Queue-Automat]
        Ein \structure{Queue-Automat (QA)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ die analog zu Kellerautomaten definiert sind.
        \begin{itemize}
            \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \to P(Q \times \Gamma^*)$
        \end{itemize}
        Im Gegensatz zu PDAs werden neue Symbole \alert{hinten} angefügt.
    \end{definition}

    \begin{example}[]
        Gegeben sei die Konfiguration $(q, a, \structure{x\alpha})$ eines Queue-Automaten und ein Schritt der Übergangsfunktion.
        \begin{align}
            \delta(q, a, \structure{x}) &= (q^\prime, \alert{yz}) \\
            \intertext{Dann ergibt sich die folgende Transition.}
            (q, a, \structure{x\alpha}) &\to (q^\prime, \epsilon, \structure{\alpha}\alert{yz})
        \end{align}
    \end{example}

    \begin{theorem}[]
        Queue-Automaten sind genauso mächtig wie Turingmaschinen.
    \end{theorem}
\end{frame}
}

\defineUnit{chomsky}{%
\begin{frame}[c]
    \frametitle{Chomsky-Hierarchie}
    \setbeamercovered{dynamic}

    \begin{center}
        \begin{tikzpicture}[auto]
            \tikzstyle{rect} = [thick];
            \tikzstyle{caption} = [align=left, anchor=north west];

            \chomsky{tumlightblue}{}{0}{Alle formalen Sprachen};
            \chomsky{tumred}{}{1}{Typ 0 - Rekursiv aufzählbar\\Grammatik\\Turingmaschine, WHILE-Programm, $\mu$-rekursive Funktion};
            \chomsky{tumblue}{}{2}{Typ 1 - Kontextsensitiv\\Längenmonotone Grammatik\\Linear Beschränkter Automat (LBA)};
            \chomsky{tumorange}{}{3}{Typ 2 - Kontextfrei\\Links nur ein Nichtterminal\\Kellerautomat (PDA)};
            \chomsky{tumgreen}{}{4}{Typ 3 - Regulär\\Links- / Rechtsreguläre Grammatik\\DFA, NFA, RE};
        \end{tikzpicture}
    \end{center}
\end{frame}
}

\defineUnit{berechenbarkeit}{%
\begin{frame}
    \frametitle{Berechenbarkeit}
    \setbeamercovered{dynamic}

    \begin{definition}[Intuitive Berechenbarkeit]
        Eine Funktion $f : \N^k \to \N$ heißt \structure{intuitiv berechenbar}, wenn es einen Algorithmus gibt, der bei Eingabe $(n_1, \ldots, n_k) \in \N^k$
        \begin{itemize}
            \item nach \alert{endlich vielen Schritten} mit Ergebnis $f(n_1, \ldots, n_k)$ hält, falls $f(\ldots)$ definiert ist,
            \item und \alert{nicht terminiert}, falls $f(\ldots)$ nicht definiert ist.
        \end{itemize}
    \end{definition}

    \vfill

    \begin{block}{Churchsche These (nicht beweisbar)}
        Turing-Maschinen können genau \alert{alle} intuitiv berechenbaren Funktionen berechnen.
    \end{block}
\end{frame}
}

\defineUnit{berechenbarkeitbeispiel}{%
\begin{frame}[c]
    \frametitle{Berechenbarkeit}
    \setbeamercovered{dynamic}

    \begin{example}[Berechenbarkeit]
        Sind die folgenden Funktionen intuitiv berechenbar?

        \begin{align*}
            f_1(n) &= \begin{cases}
                1 & \text{falls $n$ prim}\\
                0 & \text{sonst}
            \end{cases} \\
            f_2(n) &= \begin{cases}
                1 & \text{falls $n$ die ersten $n$ Ziffern von $\pi$ darstellt}\\
                0 & \text{sonst}
            \end{cases} \\
            f_3(n) &= \begin{cases}
                1 & \text{falls in $\pi$ $n$ Nullen am Stück vorkommen}\\
                0 & \text{sonst}
            \end{cases}
        \end{align*}
    \end{example}
\end{frame}
}

\defineUnit{pr}{%
\begin{frame}
    \frametitle{Primitive Rekursion}
    \setbeamercovered{dynamic}

    \begin{definition}[Basisfunktionen]
        \alert{Primitiv Rekursiv} sind:
        \begin{itemize}
            \item Die konstante Funktion \alert{0}
            \item Die \alert{Nachfolgerfunktion} $s(n) = n + 1$
            \item Die \alert{Projektionsfunktion} $\pi_i^k : \N^k \to \N, i \in [k]$
                \[ \pi_i^k(x_1, \ldots, x_k) = x_i \]
        \end{itemize}
    \end{definition}

    \begin{definition}[Komposition]
        Sind $g$ und $h_i$ PR und $\bar{x} = (x_1, \ldots, x_n)$, dann ist auch \alert{$f$} PR:
        \[ f(\bar{x}) = \alert{g(h_1(\bar{x}), \ldots, h_k(\bar{x}))} \]
    \end{definition}
\end{frame}
}

\defineUnit{prrekursion}{%
\begin{frame}
    \frametitle{Primitive Rekursion}
    \setbeamercovered{dynamic}
    \begin{block}{Basisfunktionen und Komposition}
        Schon \alert{PR} sind:
        \begin{itemize}
            \item Konstante: $0$
            \item Nachfolger: $s(n) = n + 1$
            \item Projektion: $\pi_i^k : \N^k \to \N$
            \item Komposition: $f(\bar{x}) = g(h_1(\bar{x}), \ldots, h_k(\bar{x}))$
        \end{itemize}
    \end{block}
\begin{definition}[Primitive Rekursion] Das Schema der \alert{primitiven Rekursion} erzeugt aus $g$ und $h$ die Funktion \alert{$f$}: \begin{align*} f(0, \bar{x}) &= g(\bar{x}) \\ f(\alert{m + 1}, \bar{x}) &= h(f(\alert{m}, \bar{x}), \alert{m}, \bar{x}) \end{align*} \end{definition} \end{frame} 
}

\defineUnit{prprogramme}{%
\begin{frame}
    \frametitle{PR-Programme}
    \setbeamercovered{dynamic}

    U.a. diese Programme sind laut Vorlesung oder Übung PR:
    \begin{itemize}
        \item $pred(x) = \max \left\{ 0, x - 1 \right\}$
        \item \alert{$add(x, y) = x + y$}
        \item \alert{$x \dot{-} y = \max \left\{ 0, x - y \right\}$}
        \item \alert{$mult(x, y) = x \cdot y$}
        \item $div(x, y) = x \div y$ (Ganzzahldivision)
        \item Die restliche einfache Arithmetik\ldots
            \vspace{1.5em}
        \item $tower(n) = 2^{2^{2^{\iddots}}}$ mit $tower(4) = 2^{16}$
        \item $sqr(x) = x^2$, $sqrt(x) = \sqrt{x}$
        \item $c(x), p_1(x), p_2(x)$ (Cantorsche Paarungsfunktion)
        \item $ifthen(n, a, b) = \begin{cases} a & n \neq 0 \\ b & n = 0 \end{cases}$
    \end{itemize}
\end{frame}
}

\defineUnit{prerweitert}{%
\begin{frame}
    \frametitle{Erweitertes PR-Schema}
    \setbeamercovered{dynamic}

    \begin{definition}[Erweitertes PR-Schema]
        Das \alert{erweiterte Schema der primitiven Rekursion} erlaubt
        \begin{align*}
            f(0, \bar{x}) &= t_0 \\
            f(m + 1, \bar{x}) &= t
        \end{align*}
        wobei
        \begin{itemize}
            \item $t_0$ enthält nur PR-Funktionen und die $x_i$
            \item $t$ enthält nur \alert{$f(m, \bar{x})$}, PR Funktionen, \alert{$m$} und die $x_i$.
        \end{itemize}
    \end{definition}

    \begin{theorem}
        Das erweiterte Schema der primitiven Rekursion führt nicht aus \alert{PR} heraus.
    \end{theorem}
\end{frame}
}

\defineUnit{tmif}{%
\begin{frame}
    \frametitle{Programmieren mit TMs}
    \setbeamercovered{dynamic}

    Sind $f_1$ und $f_2$ Endzustände von $M$, so bezeichnet
    \begin{center}
        \begin{tikzpicture}
            \node (M) at (0, 0) {$M$};
            \node[above right=0.2cm and 1cm of M] (M1) {$M_1$};
            \node[below right=0.2cm and 1cm of M] (M2) {$M_2$};
            \coordinate[right of=M1] (M1s);
            \coordinate[right of=M2] (M2s);

            \draw[every edge] (-1, 0) -- (M);
            \draw[every edge] (M) -- node[above left] {$f_1$} (M1);
            \draw[every edge] (M) -- node[below left] {$f_2$} (M2);
            \draw[every edge] (M1) -- (M1s);
            \draw[every edge] (M2) -- (M2s);
        \end{tikzpicture}
    \end{center}
    eine \alert{Fallunterscheidung}.\\
    \begin{example}[Band=0?]
    \begin{align*}
        \delta(q_0, 0) &= (q_0, 0, R) \\
        \delta(q_0, \square) &= (ja, \square, L) \\
        \delta(q_0, a) &= (nein, a, N) \qquad \text{für } a \neq 0, \square
    \end{align*}
    \end{example}
\end{frame}
}

\defineUnit{while}{%
\begin{frame}
    \frametitle{WHILE-Programme}
    \setbeamercovered{dynamic}

    \begin{definition}[WHILE-Programm]
        Syntax von \alert{WHILE-Programmen}.\\
        Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$.
        \begin{align*}
            P &\rightarrow X := X + C \\
            &\mid X := X - C \\
            &\mid P; P \\
            &\mid \alert{\mathbf{WHILE}\  X \neq 0 \ \mathbf{DO}\  P \ \mathbf{END}} \\
            &\mid \textcolor{gray}{\mathbf{LOOP}\  X \ \mathbf{DO}\  P \ \mathbf{END}} \\
            &\mid \textcolor{gray}{\mathbf{IF}\  X = 0 \ \mathbf{DO}\  P \ \mathbf{ELSE}\  Q \ \mathbf{END}}
        \end{align*}
    \end{definition}

    \begin{itemize}
        \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0.
        \item Semantik wie erwartet.
    \end{itemize}
\end{frame}
}

\defineUnit{goto}{%
\begin{frame}
    \frametitle{GOTO-Programme}
    \setbeamercovered{dynamic}

    \begin{definition}[GOTO-Programm]
        Syntax von \alert{GOTO-Programmen}.\\
        Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. \\
        Alle Anweisungen haben eine Markierung \alert{$M_1 : A_1; M_2 : A_2$}.
        \begin{align*}
            P &\rightarrow X := X + C \\
            &\mid X := X - C \\
            &\mid P; P \\
            &\mid \mathbf{GOTO}\  M_i \\
            &\mid \mathbf{IF}\  X = 0 \ \mathbf{GOTO}\  M_i \\
            &\mid \mathbf{HALT}
        \end{align*}
    \end{definition}

    \begin{itemize}
        \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0.
    \end{itemize}
\end{frame}
}

\defineUnit{loop}{%
\begin{frame}
    \frametitle{LOOP-Programme}
    \setbeamercovered{dynamic}

    \begin{definition}[LOOP-Programm]
        Syntax von \alert{LOOP-Programmen}.\\
        Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$.
        \begin{align*}
            P &\rightarrow X := X + C \\
            &\mid X := X - C \\
            &\mid P; P \\
            &\mid \mathbf{LOOP}\  X \ \mathbf{DO}\  P \ \mathbf{END} \\
            &\mid \textcolor{gray}{\mathbf{IF}\  X = 0 \ \mathbf{DO}\  P \ \mathbf{ELSE}\  Q \ \mathbf{END}}
        \end{align*}
    \end{definition}

    \begin{itemize}
        \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0.
        \item $\mathbf{LOOP}\  x_i \ \mathbf{DO}\  P \ \mathbf{END}$ führt $P$ genau $n$ mal aus, wobei $n$ der Anfangswert von $x_i$ ist. \alert{Zuweisungen an $x_i$ in $P$ ändern die Anzahl der Durchläufe nicht.}
    \end{itemize}
\end{frame}
}

\defineUnit{prmax}{%
\begin{frame}
    \frametitle{Beschränkte Operationen}
    \setbeamercovered{dynamic}
    \begin{definition}
        Ein Prädikat $P$ ist \alert{PR}, wenn es eine PR Funktion $\hat{P}$ gibt mit 
        \[\hat{P}(x) = 1 \Longleftrightarrow P(x)\]
    \end{definition}

    \begin{definition}[Beschränkte Operationen]
        Ist $P$ PR, dann auch 
        \begin{itemize}
            \item der \alert{beschränkte max-Operator}
                \[\max \left\{ x \alert{\leq n} \mid P(x) \right\}, \quad \max \left\{ \emptyset \right\} = 0\]
            \item der \alert{beschränkte Existenzquantor}
                \[\exists x \alert{\leq n}. P(x)\]
        \end{itemize}
    \end{definition}
\end{frame}
}

\defineUnit{murekursion}{%
\begin{frame}
    \frametitle{$\mu$-Rekursion}
    \setbeamercovered{dynamic}

    \begin{definition}[$\mu$-Operator]
        Sei $f: \N^{k+1} \to \N$ eine Funktion.\\Der \alert{$\mu$-Operator} definiert eine neue Funktion $\mu f : \N^k \to \N$:
        \[(\mu f)(\bar{x}) := \begin{cases} \min \left\{ n \in \N \mid \alert{f (n, \bar{x}) = 0}\right\} & \text{falls } n \text{ existent\alert{$^*$}} \\ \perp & \text{sonst}\end{cases}\]
    \end{definition}

    \vfill

    \begin{itemize}
        \item \alert{$^*$}Für alle \alert{$m \leq n$} muss $f$ definiert sein: $f(m, \bar{x}) \neq \perp$
        \item PR + $\mu$ = $\mu$-Rekursion
        \item In Pseudocode:
            \begin{align*}
                \mu f(\bar{x}) &= find(0, \bar{x}) \\
                find(n, \bar{x}) &= \mathbf{if}\  f(n, \bar{x}) = 0 \ \mathbf{then}\  n \ \mathbf{else}\  find(n+1, \bar{x})
            \end{align*}
    \end{itemize}
\end{frame}
}

\defineUnit{modelluebersetzungen}{%
\begin{frame}
    \frametitle{Übersetzungen}
    \setbeamercovered{dynamic}

    \begin{center}
        \begin{tikzpicture}[node distance=2.5cm]
            \node (WH) {WHILE};
            \node (GO) [above left of = WH] {GOTO};
            \node (TM) [above right of = WH] {TM};
            \node (LO) [below of = WH] {LOOP};
            \node (PR) [left of = LO] {PR};
            \node (MR) [left of = WH] {$\mu$R};

            \draw [every edge, ->] (LO) -- (WH);
            \draw [every edge, ->] (PR) -- (MR);
            \draw [every edge, tumgreen, <->] (LO) -- (PR);
            \draw [every edge, tumgreen, <->] (WH) -- (MR);
            \draw [every edge, <->] (WH) -- (GO);
            \draw [every edge, ->] (WH) -- (TM);
            \draw [every edge, ->] (TM) -- (GO);
        \end{tikzpicture}
    \end{center}

    \vfill

    LOOP kann in WHILE \alert{übersetzt} werden, WHILE ist also \alert{mindestens so mächtig} wie LOOP (sogar mächtiger).
\end{frame}
}

\defineUnit{entscheidbarkeit}{%
\begin{frame}
    \frametitle{Entscheidbarkeit}
    \setbeamercovered{dynamic}

    \begin{definition}[Entscheidbarkeit]
        Eine Menge $A$ heißt \structure{entscheidbar} gdw ihre \alert{charakteristische Funktion}
        \[ \chi_A(x) := \begin{cases}1 & \text{falls } x \in A \\ 0 & \text{falls } x \not \in A \end{cases} \]
        berechenbar ist.
    \end{definition}

    \vfill

    \begin{definition}[Semi-Entscheidbarkeit]
        Eine Menge $A$ heißt \structure{semi-entscheidbar} gdw
        \[ \chi'_A(x) := \begin{cases}1 & \text{falls } x \in A \\ \perp & \text{falls } x \not \in A \end{cases} \]
        berechenbar ist.
    \end{definition}
\end{frame}
}

\defineUnit{breduktion}{%
\begin{frame}
    \frametitle{Reduzierbarkeit}
    \setbeamercovered{dynamic}

    \begin{definition}[Reduzierbarkeit]
        Eine Menge $A \subseteq \Sigma^*$ ist \alert{reduzierbar} auf eine Menge $B \subseteq \Gamma^*$ gdw es eine totale und berechenbare Funktion $f:\Sigma^* \to \Gamma^*$ gibt mit
        \[\forall w \in \Sigma^*. w \in A \Longleftrightarrow f(w) \in B\]
        Wir schreiben dann \alert{$A \leq B$}.
    \end{definition}

    \vfill

    \structure{Intuition}:
    \begin{itemize}
        \item $B$ ist \alert{mindestens so schwer} zu lösen wie $A$
        \item Ist $A$ unlösbar, dann auch $B$.
        \item Ist $B$ lösbar, dann erst recht $A$.
    \end{itemize}
\end{frame}
}

\defineUnit{spezielleshalteproblem}{%
\begin{frame}
    \frametitle{Spezielles Halteproblem}
    \setbeamercovered{dynamic}

    \begin{definition}[Spezielles Halteproblem]
        Gegeben ein \structure{Wort} $w \in \left\{ 0, 1 \right\}^*$.\\
        Hält \alert{$M_w$} bei Eingabe \alert{$w$}?
        \[\alert{K} := \left\{ w \mid M_w[w]\downarrow \right\}\]
    \end{definition}

    \begin{theorem}[]
        Das spezielle Halteproblem ist \alert{nicht entscheidbar}.
    \end{theorem}

    \vfill

    \begin{itemize}
        \item Hält eine Turingmaschine mit sich selbst als Eingabe?
        \item $w$ ist die \structure{Gödelisierung} von $M_w$.
        \item $K$ ist semi-entscheidbar, $\overline{K}$ \alert{nicht}.
    \end{itemize}
\end{frame}
}

\defineUnit{halteproblem}{%
\begin{frame}
    \frametitle{Allgemeines Halteproblem}
    \setbeamercovered{dynamic}

    \begin{definition}[Allgemeines Halteproblem]
        Gegeben \structure{Wörter} $w, x \in \left\{ 0, 1 \right\}^*$.\\
        Hält \alert{$M_w$} bei Eingabe \alert{$x$}?
        \[\alert{H} := \left\{ w\#x \mid M_w[x]\downarrow \right\}\]
    \end{definition}

    \begin{theorem}[]
        Das allgemeine Halteproblem ist \alert{nicht entscheidbar}.
    \end{theorem}

    \vfill

    \begin{itemize}
        \item Es ist $K \leq H$. Warum?
    \end{itemize}
\end{frame}
}

\defineUnit{aufzaehlbarkeit}{%
\begin{frame}
    \frametitle{Rekursive Aufzählbarkeit}
    \setbeamercovered{dynamic}

    \begin{definition}[Rekursiv aufzählbar]
        Eine Menge $A$ heißt \alert{rekursiv aufzählbar} wenn $A = \emptyset$ oder es eine \alert{berechenbare} totale Funktion $f : \N \to A$ gibt, so dass
        \[A = \left\{ f(0), f(1), \ldots \right\} = \bigcup_{n \in \N} \left\{ f(n) \right\}\]
    \end{definition}

    \vfill

    \structure{Äquivalent:}
    \begin{itemize}
        \item $A$ rekursiv aufzählbar
        \item $A$ semi-entscheidbar, also $\chi'_A$ berechenbar
        \item $A=L(M)$ für eine TM $M$
        \item $A$ ist Bild oder Urbild einer berechenbaren Funktion
    \end{itemize}
\end{frame}
}

\defineUnit{rice}{%
\begin{frame}
    \frametitle{Satz von Rice}
    \setbeamercovered{dynamic}

    \begin{theorem}[Rice]
        Sei $F$ eine Menge berechenbarer Funktionen.\\
        Sei weder $F = \emptyset$ noch $F = \text{alle ber. Funktionen}$ (\alert{$F$ nicht trivial}).\\
        Dann ist \alert{unentscheidbar}, ob die von einer gegebenen TM $M_w$ berechnete Funktion in $F$ ist, also ob \alert{$\varphi_w \in F$}.
    \end{theorem}

    \begin{itemize}
        \item Nicht-triviale \alert{semantische} Eigenschaften von Programmen sind unentscheidbar.
        \item \alert{Termination} ist unentscheidbar.
    \end{itemize}

    \vfill

    \structure{Rice-Shapiro:}
    \begin{itemize}
        \item Termination ist nicht semi-entscheidbar.
        \item Nicht-Termination ist nicht semi-entscheidbar.
    \end{itemize}
\end{frame}
}

\defineUnit{pcp}{%
\begin{frame}
    \frametitle{PCP}
    \setbeamercovered{dynamic}

    \begin{definition}[Postsches Korrespondenzproblem]
        Gegeben \structure{endliche Folge} $(x_1, y_1), \ldots, (x_k, y_k)$ mit $x_i, y_i \in \Sigma^+$.\\
        Gibt es eine \alert{Folge von Indizes} $i_1, \ldots, i_n \in \left\{ 1, \ldots, k \right\}$ mit \alert{\[x_{i_1}, \ldots, x_{i_n} = y_{i_1}, \ldots, y_{i_n}\]}
    \end{definition}

    \vfill

    \begin{center}
        \begin{tikzpicture}
            \begin{scope}[start chain, node distance=2em]
                \node[tape, active] {\pcp{$x_i$}{$y_i$}};
                \node[tape] (a) {\pcp{$001$}{$00$}};
                \node[tape] (b) {\pcp{$10$}{$11$}};
                \node[tape] (c) {\pcp{$1$}{$01$}};
            \end{scope}
            \node[below of=a] {$1$};
            \node[below of=b] {$2$};
            \node[below of=c] {$3$};
        \end{tikzpicture}
    \end{center}

    \vfill

    \begin{theorem}[]
        Das PCP ist \alert{unentscheidbar}, aber semi-entscheidbar.
    \end{theorem}
\end{frame}
}

\defineUnit{pcpbeispiel}{%
\begin{frame}
    \frametitle{PCP lösen}
    \setbeamercovered{dynamic}

    \begin{block}{Idee}
        \alert{Mögliche Lösungen} aufzählen, richtige Lösungen identifizieren
    \end{block}

    \begin{center}
        \begin{tikzpicture}
            \begin{scope}[start chain, node distance=2em]
                \node[tape, active] {\pcp{$x_i$}{$y_i$}};
                \node[tape] (a) {\pcp{$001$}{$00$}};
                \node[tape] (b) {\pcp{$01$}{$10$}};
                \node[tape] (c) {\pcp{$1$}{$11$}};
            \end{scope}
            \node[below of=a] {$1$};
            \node[below of=b] {$2$};
            \node[below of=c] {$3$};
        \end{tikzpicture}

        \vspace{2em}

        \begin{tikzpicture}[grow=right, level distance = 2cm]
            \tikzstyle{every node} = []
            \tikzstyle{residual} = [rectangular, thin, fill=tumgreen!10, font=\scriptsize]
            \tikzstyle{edge from parent} = [every edge]

            \tikzstyle{level 1} = [sibling distance = 1.7cm]
            \tikzstyle{level 2} = [sibling distance = 1.1cm]

            \node[residual] {}
            child {
                node[residual] {\pcp{$1$}{}}
                child {
                    node[residual] {\pcp{$1$}{}}
                    child {
                        node[residual] {\pcp{$1$}{}}
                        child {
                            node[residual]{$\ldots$}
                            edge from parent
                        }
                        edge from parent
                        node[below] {$2$}
                    }
                    child {
                        node[residual, active] {\pcp{}{}}
                        edge from parent
                        node[above] {$3$}
                    }
                    edge from parent
                    node[below] {$2$}
                }
                child {
                    node[residual, active] {\pcp{}{}}
                    edge from parent
                    node[above] {$3$}
                }
                edge from parent
                node[below] {$1$}
            }
            child {
                node[residual]{\pcp{}{$1$}}
                child {
                    node[residual]{\pcp{}{$11$}}
                    child {
                        node[residual]{$\ldots$}
                        edge from parent
                        node[above] {$3$}
                    }
                    edge from parent
                    node[above] {$3$}
                }
                edge from parent
                node[above] {$3$}
            };

            \uncover<2>{\node at (10cm, 0) {$L = \left\{ (12^*3)^+ \right\}$};}
        \end{tikzpicture}
    \end{center}
\end{frame}
}

\defineUnit{time}{%
\begin{frame}[t]
    \frametitle{$TIME$}
    \setbeamercovered{dynamic}

    \begin{definition}[$TIME$]
        Wir bezeichnen die minimale Anzahl der Schritte, bis eine \structure{DTM} $M$ mit Eingabe $w$ hält als $\alert{time_M(w)} \in \N \cup \left\{ \infty \right\}$.\\
        \vspace{1em}
        Sei $f : \N \to \N$ total. Dann ist
        \begin{align*}
            \alert{TIME(f(n))} := \{ A \subseteq \Sigma^* \mid \exists &\structure{DTM}\  M. A = L(M) \wedge \\
        &\forall w \in \Sigma^*. \structure{time_M(w) \leq f(|w|)} \}
        \end{align*}
        die Klasse der \structure{in Zeit $f(n)$} von einer \structure{DTM} entscheidbaren Sprachen.
    \end{definition}

    \vfill

    \begin{itemize}
        \item $TIME(\Oh(n))$ enthält alle "\structure{linearen Probleme}".
        \item Also alle Probleme, für die ein Linearzeitalgorithmus existiert.
    \end{itemize}
\end{frame}
}

\defineUnit{ntime}{%
\begin{frame}[t]
    \frametitle{$NTIME$}
    \setbeamercovered{dynamic}

    \begin{definition}[$NTIME$]
        Wir bezeichnen die minimale Anzahl der Schritte, bis eine \structure{NTM} $M$ mit Eingabe $w$ hält als $\alert{ntime_M(w)} \in \N$. 
        \[ \alert{ntime_M(w)} := \begin{cases} \text{minimale Schrittanzahl} & \text{falls } w \in L(M) \\ 0 & \text{falls } w \not \in L(M)\end{cases} \]
        Dann ist
        \begin{align*}
            \alert{NTIME(f(n))} := \{ A \subseteq \Sigma^* \mid \exists &\structure{NTM}\  M. A = L(M) \wedge \\
        &\forall w \in \Sigma^*. \structure{ntime_M(w) \leq f(|w|)} \}
        \end{align*}
        die Klasse der \structure{in Zeit $f(n)$} von einer \structure{NTM} entscheidbaren Sprachen.
    \end{definition}
\end{frame}
}

\defineUnit{pundnp}{%
\begin{frame}
    \frametitle{P und NP}
    \setbeamercovered{dynamic}

    \begin{definition}
        \alert{P} ist die Menge aller von einer \structure{DTM} in polynomieller Zeit entscheidbaren Sprachen.
        \[\alert{P}:= \bigcup_{p\text{ Polynom}} TIME(p(n)) = \bigcup_{k \in \N} TIME(\alert{\Oh(n^k)}) \]
    \end{definition}

    \begin{definition}
        \alert{NP} ist die Menge aller von einer \structure{NTM} in polynomieller Zeit entscheidbaren Sprachen.
        \[\alert{NP}:= \bigcup_{p\text{ Polynom}} NTIME(p(n)) = \bigcup_{k \in \N} NTIME(\alert{\Oh(n^k)}) \]
    \end{definition}
\end{frame}
}

\defineUnit{verifikator}{%
\begin{frame}
    \frametitle{Verifikator}
    \setbeamercovered{dynamic}

    \begin{definition}[Verifikator]
        Sei $M$ eine \structure{DTM} mit $L(M) \subseteq \left\{ w\# c \mid w \in \Sigma^*, c \in \Delta^* \right\}$.
        \begin{itemize}
            \item Falls $w\#c \in L(M)$, dann heißt $c$ \alert{Zertifikat} für $w$.
            \item $M$ ist ein \alert{polynomiell beschränkter Verifikator} für
                \[\left\{ \structure{w \in \Sigma^*} \mid \exists c \in \Delta^* . w\#c \in L(M) \right\}\]
                falls $time_M(w\#c) \leq p(|w|)$ für ein Polynom $p$.
        \end{itemize}
    \end{definition}

    \begin{itemize}
        \item \structure{NTM} rät Lösung (Zertifikat), \structure{DTM} probiert sie aus.
        \item Verifizieren (wahrscheinlich) einfacher als Lösung finden.
    \end{itemize}

    \vfill

    \begin{theorem}
        \alert{$A \in NP$} gdw es einen pol. beschränkten Verifikator für A gibt.
    \end{theorem}
\end{frame}
}

\defineUnit{preduktion}{%
\begin{frame}
    \frametitle{Polynomielle Reduzierbarkeit}
    \setbeamercovered{dynamic}

    \begin{definition}[Polynomielle Reduzierbarkeit]
        Eine Menge $A \subseteq \Sigma^*$ ist \alert{polynomiell reduzierbar} auf eine Menge $B \subseteq \Gamma^*$ gdw es eine totale und \structure{von einer DTM in polynomieller Zeit} berechenbare Funktion $f:\Sigma^* \to \Gamma^*$ gibt mit
        \[\forall w \in \Sigma^*. w \in A \Longleftrightarrow f(w) \in B\]
        Wir schreiben dann \alert{$A \leq_P B$}.
    \end{definition}

    \vfill

    \begin{itemize}
        \item Die Relation $\leq_P$ ist \structure{transitiv}.
        \item P und NP sind \structure{nach unten abgeschlossen}:
            \[A \leq_P B \in P/NP \Longrightarrow A \in P/NP\]
    \end{itemize}
\end{frame}
}

\defineUnit{npvollstaendigkeit}{%
\begin{frame}
    \frametitle{NP-Vollständigkeit}
    \setbeamercovered{dynamic}

    \begin{definition}[NP-Schwere]
        Eine Sprache $L$ heißt \alert{NP-schwer} (NP-hart) wenn sich \structure{alle Sprachen} in NP auf $L$ reduzieren lassen.
        \[\forall A \in NP. A \leq_P L\]
    \end{definition}

    \begin{definition}[NP-Vollständigkeit]
        Eine Sprache $L$ heißt \alert{NP-vollständig} wenn $L$ \structure{NP-schwer} ist und \structure{$L \in NP$}.
    \end{definition}

    \vfill

    \structure{Fragen}:
    \begin{itemize}
        \item Gibt es überhaupt NP-vollständige Sprachen?
        \item Gibt es eine NP-vollständige Sprache in $P$?
    \end{itemize}
\end{frame}
}

\defineUnit{sat}{%
\begin{frame}
    \frametitle{SAT}
    \setbeamercovered{dynamic}

    \begin{definition}[Aussagenlogik]
        Syntax der \alert{Aussagenlogik}.\\
        \begin{description}
            \item[Formeln] $F \rightarrow \neg F \mid (F \wedge F) \mid (F \vee F) \mid X$
            \item[Variablen] $X \rightarrow x \mid y \mid z \mid \ldots$
        \end{description}
    \end{definition}

    \vfill

    \begin{definition}[SAT]
        Gegeben eine \structure{aussagenlogische Formel} $F$.\\
        Ist $F$ \alert{erfüllbar}, also gibt es eine Belegung der Variablen in $F$, sodass $F$ gilt?
    \end{definition}

    \begin{theorem}[Cook 1971]
        $\mathbf{SAT}$ ist \alert{NP-vollständig}.
    \end{theorem}
\end{frame}
}

\defineUnit{3col}{%
\begin{frame}
    \frametitle{3COL}
    \setbeamercovered{dynamic}

    \begin{definition}[3COL]
        Gegeben ein \structure{Graph} $G = (V, E)$.\\
        Gibt es eine \alert{Färbung der Knoten} $V$ mit $3$ Farben, so dass keine zwei benachbarten Knoten die gleiche Farbe haben?
    \end{definition}

    \vfill

    \begin{center}
        \begin{tikzpicture}
            \tikzstyle{red} = [fill=tumred!50]
            \tikzstyle{green} = [fill=tumgreen!50]
            \tikzstyle{blue} = [fill=tumblue!50]
            \tikzstyle{vertex} = [draw, circle, thin, blue]
            \tikzstyle{edge} = [draw, thick]

            \foreach \name/\angle/\dist/\col in {
                ia/18/0.8cm/blue, ib/90/0.8cm/red, ic/162/0.8cm/red, id/234/0.8cm/green, ie/306/0.8cm/green,
                oa/18/1.6cm/red, ob/90/1.6cm/blue, oc/162/1.6cm/green, od/234/1.6cm/red, oe/306/1.6cm/blue} {
                \node<1>[vertex] (\name) at (\angle:\dist) {};
                \node<2>[vertex, \col] (\name) at (\angle:\dist) {};
            }

            \foreach \a/\b in {
                ia/oa, ib/ob, ic/oc, id/od, ie/oe,
                oa/ob, ob/oc, oc/od, od/oe, oe/oa,
                ia/ic, ic/ie, ie/ib, ib/id, id/ia} {
                \draw[edge] (\a) -- (\b);
            }
        \end{tikzpicture}
    \end{center}

    \begin{theorem}
        Es ist \alert{$\mathbf{3COL} \leq_P \mathbf{SAT}$} und $\alert{\mathbf{SAT}} \leq_P \mathbf{3SAT} \alert{\leq_P \mathbf{3COL}}$.
    \end{theorem}
\end{frame}
}

\defineUnit{typ0sprachen}{%
\begin{frame}
    \frametitle{Typ 0 Sprachen}
    \setbeamercovered{dynamic}

    \begin{center}
        \begin{tikzpicture}[node distance=2.5cm]
            \node (WH) {WHILE};
            \node (GO) [above left of = WH] {GOTO};
            \node (TM) [above right of = WH] {TM};
            \node (MR) [left of = WH] {$\mu$R};

            \draw [every edge, tumgreen, <->] (WH) -- (MR);
            \draw [every edge, <->] (WH) -- (GO);
            \draw [every edge, ->] (WH) -- (TM);
            \draw [every edge, ->] (TM) -- (GO);
        \end{tikzpicture}
    \end{center}

    \vfill

    \begin{theorem}[]
        Sei $A$ formale Sprache, dann ist äquivalent:
        \vspace{1em}
        \begin{itemize}
            \item $A$ ist \structure{Typ 0 Sprache}
            \item $A$ \structure{rekursiv aufzählbar}
            \item $A$ \structure{semi-entscheidbar}, also $\chi'_A$ berechenbar
            \item $A=L(M)$ für eine \structure{TM $M$}
            \item $A$ ist \structure{Bild oder Urbild} einer berechenbaren Funktion
        \end{itemize}
    \end{theorem}
\end{frame}
}

\defineUnit{spracheigenschaften}{%
\begin{frame}
    \frametitle{Spracheigenschaften}
    \setbeamercovered{dynamic}

    \begin{itemize}
        \item Abschlusseigenschaften
    \end{itemize}
    \begin{table}
        \begin{tabu}to \textwidth{X[c]|ccccc}
            & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{}
            REG & ja & ja & ja & ja & ja\\
            CFL & nein & ja & nein & ja & ja\\
            CSL & ja & ja & ja & ja & ja\\
            TM & \structure{ja} & \structure{ja} & \structure{nein} & \structure{ja} & \structure{ja}
        \end{tabu}
    \end{table}

    \vfill

    \begin{itemize}
        \item Entscheidbarkeit
    \end{itemize}
    \begin{table}
        \begin{tabu}to \textwidth{X[c]|cccc}
            & Wortproblem & Leerheit & Äquivalenz & Schnittproblem\\ \tabucline{}
            DFA & $\Oh(n)$ & ja & ja & ja\\
            CFG & $\Oh(n^3)$ & ja & nein & nein\\
            CSL & $\Oh(2^n)$ & nein & nein & nein\\
            TM & \structure{nein} & \structure{nein} & \structure{nein} & \structure{nein}
        \end{tabu}
    \end{table}
\end{frame}
}

\defineUnit{formalesprachen}{%
\begin{frame}[c]
    \frametitle{Formale Sprachen}
    \setbeamercovered{dynamic}

    \begin{center}
        \begin{tikzpicture}[auto]
            \tikzstyle{rect} = [thick];
            \tikzstyle{caption} = [align=left, anchor=north west];

            \definecolor{hannahyellow}{HTML}{FFB81C}
            \langclass{brown}{}{0}{Formale Sprache $\subseteq \Sigma^*$};
            \langclass{tumblue}{}{1}{Typ 0 - Semi-Entscheidbar};
            \langclass{tumgreen}{}{2}{Entscheidbar};
            \langclass{violet}{}{3}{LOOP, PR};
            \langclass{tumred}{}{4}{NP};
            \langclass{hannahyellow}{dashed}{5}{P};
            \langclass{tumgreen!40!black}{}{6}{Typ 2 - Kontextfrei};
            \langclass{tumlightblue!80!black}{}{7}{Typ 3 - Regulär};
            \langclass{tumblue!20!black}{}{8}{Endlich};
        \end{tikzpicture}
    \end{center}
\end{frame}
}