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

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

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

    \begin{definition}[Turingmaschine]
        Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
        \begin{itemize}
            \item \alert{Ü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 \alert{Konfiguration} ist ein Tripel $(\alpha, q, \beta) \in \Gamma^* \times Q \times \Gamma^*$. \\
        Dies modelliert eine TM mit:
        \begin{itemize}
            \item \alert{Bandinhalt} $\ldots\square\alpha\beta\square\ldots$
            \item \alert{Zustand} $q$
            \item Kopf auf dem \alert{ersten Zeichen} von $\beta\square$
        \end{itemize}
        Die \alert{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$ \alert{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 \alert{nichtdeterministische} Turingmaschine (TM) ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
        \begin{itemize}
            \item \ldots
            \item \alert{Ü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{chomsky}{%
\begin{frame}[c]
    \frametitle{Chomsky-Hierarchie}
    \setbeamercovered{dynamic}

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

            \draw[rect, tumblue, fill=tumblue!10] (5.5, 0) rectangle (-5.5, 7) node[caption] {Berechenbare Funktionen};
            \draw[rect, dashed, tumred, fill=tumred!10] (4.5, 0.3) rectangle (-4.5, 6) node[caption] {Typ 0 - Rekursiv aufzählbar\\Turingmaschinen, $\lambda$-Kalkül};
            \draw[rect, tumivory, fill=tumivory!10] (3.5, 0.6) rectangle (-3.5, 4.8) node[caption] {Typ 1 - Kontextsensitiv\\CSG};
            \draw[rect, tumorange, fill=tumorange!10] (2.5, 0.9) rectangle (-2.5, 3.6) node[caption] {Typ 2 - Kontextfrei\\PDA, CFG};
            \draw[rect, tumgreen, fill=tumgreen!10] (1.5, 1.2) rectangle (-1.5, 2.4) node[caption] {Typ 3 - Regulär\\DFA, 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 \alert{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 \alert{$add(x, y) = x + y$}
        \item \alert{$mult(x, y) = x \cdot y$}
        \item $pred(x) = \max \left\{ 0, x - 1 \right\}$
        \item \alert{$x \dot{-} y = \max \left\{ 0, x - y \right\}$}
        \item $div(x, y) = x \div y$ (Ganzzahldivision)
        \item $mod(x, y) = x \mod y$
            \vspace{1.5em}
        \item $tower(n) = 2^{2^{2^{\iddots}}}$ mit $tower(4) = 2^{16}$
        \item $sqr(x) = x^2$
        \item $twopow(n) = 2^n$
        \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 \alert{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}

    \begin{definition}[Semi-Entscheidbarkeit]
        Eine Menge $A$ heißt \alert{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$ unlö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}
}