--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/computation.tex	Thu Jul 11 20:42:36 2013 +0200
@@ -0,0 +1,686 @@
+\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{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{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}
+}