--- a/notes/tex/ue10_notes.tex	Thu Jul 11 21:57:50 2013 +0200
+++ b/notes/tex/ue10_notes.tex	Thu Jul 11 22:06:26 2013 +0200
@@ -1,182 +1,17 @@
 \input{preamble.tex}
+\input{frames.tex}
 
 \title{Übung 10: $\mu$Rekursion, Entscheidbarkeit}
 \subtitle{Theoretische Informatik Sommersemester 2013}
 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
 
 \begin{document}
-
-\begin{frame}
-    \titlepage
-\end{frame}
-
-\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}
-
-\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}
-
-\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}
-
-\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}
-
-\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}
-
-\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}
-
-\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}
-
-\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}
-
+\showUnit{titel}
+\showUnit{loop}
+\showUnit{prerweitert}
+\showUnit{prmax}
+\showUnit{murekursion}
+\showUnit{berechenbarkeit}
+\showUnit{entscheidbarkeit}
+\showUnit{breduktion}
 \end{document}