--- a/notes/tex/computation.tex	Thu Jul 11 21:25:21 2013 +0200
+++ b/notes/tex/computation.tex	Thu Jul 11 21:57:50 2013 +0200
@@ -120,6 +120,28 @@
 \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}
@@ -471,6 +493,28 @@
 \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}