Binary file notes/complete_notes.pdf has changed

--- a/notes/tex/complete_notes.tex	Sun Jun 29 16:58:20 2014 +0200
+++ b/notes/tex/complete_notes.tex	Fri Jul 04 21:18:30 2014 +0200
@@ -80,6 +80,14 @@
 \showUnit{prerweitert}
 \showUnit{prprogramme}
 \showUnit{loop}
+
+%ue11
 \showUnit{berechenbarkeit}
 \showUnit{berechenbarkeitbeispiel}
+\showUnit{entscheidbarkeit}
+\showUnit{breduktion}
+\showUnit{spezielleshalteproblem}
+\showUnit{halteproblem}
+\showUnit{aufzaehlbarkeit}
+\showUnit{rice}
 \end{document}

--- a/notes/tex/computation.tex	Sun Jun 29 16:58:20 2014 +0200
+++ b/notes/tex/computation.tex	Fri Jul 04 21:18:30 2014 +0200
@@ -573,14 +573,14 @@
     \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
+        Eine Menge $A \subseteq \Sigma^*$ heißt \structure{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$}.
+        Wir schreiben dann \structure{$A \leq B$}.
     \end{definition}
 
     \vfill
 
-    \structure{Intuition}:
+    Intuitiv gilt:
     \begin{itemize}
         \item $B$ ist \alert{mindestens so schwer} zu lösen wie $A$
         \item Ist $A$ unlösbar, dann auch $B$.
@@ -595,22 +595,17 @@
     \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\}\]
+        Gegeben ein Wort $w \in \left\{ 0, 1 \right\}^*$ und die durch \structure{Gödelisierung} kodierte Turingmaschine \structure{$M_w$}.\\
+        Die als \structure{spezielles Halteproblem} bezeichnete Sprache \structure{$K$} enthält alle Turingmaschinen, die bei sich selbst als Eingabe halten.
+        \[\structure{K} \defeq \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}
+    \begin{theorem}[]
+        Das spezielle Halteproblem ist \alert{semi-entscheidbar}, aber es ist \alert{nicht entscheidbar}.\\
+        $\overline{K}$ ist also \alert{nicht semi-entscheidbar}.
+    \end{theorem}
 \end{frame}
 }
 
@@ -620,13 +615,16 @@
     \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\}\]
+        Gegeben Wörter $w, x \in \left\{ 0, 1 \right\}^*$ und die durch \structure{Gödelisierung} kodierte Turingmaschine \structure{$M_w$}.\\
+        Die als \structure{allgemeines Halteproblem} bezeichnete Sprache \structure{$H$} enthält alle Paare $M_w$ und $x$, sodass $M_w$ bei Eingabe $x$ hält.
+        \[\structure{H} := \left\{ w\#x \mid M_w[x]\downarrow \right\}\]
     \end{definition}
 
+    \vfill
+
     \begin{theorem}[]
-        Das allgemeine Halteproblem ist \alert{nicht entscheidbar}.
+        Das allgemeine Halteproblem ist \alert{semi-entscheidbar}, aber es ist \alert{nicht entscheidbar}.\\
+        $\overline{H}$ ist also \alert{nicht semi-entscheidbar}.
     \end{theorem}
 
     \vfill
@@ -643,19 +641,23 @@
     \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
+        Eine Menge $A$ heißt \structure{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}
+    \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}
 }
 
@@ -665,23 +667,31 @@
     \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$}.
+        Sei $F$ eine \structure{Menge berechenbarer Funktionen}.\\
+        Sei weder $F = \emptyset$ noch $F = \left\{ f \mid f \text{ berechenbar} \right\}$ (\alert{$F$ nicht trivial}).\\
+        Der \structure{Satz von Rice} besagt, dass es dann \alert{unentscheidbar} ist, ob die von einer gegebenen TM $M_w$ berechnete Funktion in $F$ ist.\\
+        Die formale Sprache
+        \begin{align}
+            \left\{ w \in \Sigma^* \mid \varphi_w \in F \right\}
+        \end{align}
+        ist \alert{unentscheidbar}.
     \end{theorem}
 
+    \vfill
+
+    Intuitiv gilt:
     \begin{itemize}
         \item Nicht-triviale \alert{semantische} Eigenschaften von Programmen sind unentscheidbar.
         \item \alert{Termination} ist unentscheidbar.
     \end{itemize}
 
-    \vfill
+    % \vfill
 
-    \structure{Rice-Shapiro:}
-    \begin{itemize}
-        \item Termination ist nicht semi-entscheidbar.
-        \item Nicht-Termination ist nicht semi-entscheidbar.
-    \end{itemize}
+    % \structure{Rice-Shapiro:}
+    % \begin{itemize}
+    %     \item Termination ist nicht semi-entscheidbar.
+    %     \item Nicht-Termination ist nicht semi-entscheidbar.
+    % \end{itemize}
 \end{frame}
 }
 

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue11_notes.tex	Fri Jul 04 21:18:30 2014 +0200
@@ -0,0 +1,18 @@
+\input{preamble.tex}
+\input{frames.tex}
+
+\title{Übung 11: Berechenbarkeitstheorie}
+\subtitle{Theoretische Informatik Sommersemester 2014}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+\showUnit{titel}
+\showUnit{berechenbarkeit}
+\showUnit{berechenbarkeitbeispiel}
+\showUnit{entscheidbarkeit}
+\showUnit{breduktion}
+\showUnit{spezielleshalteproblem}
+\showUnit{halteproblem}
+\showUnit{aufzaehlbarkeit}
+\showUnit{rice}
+\end{document}

Binary file notes/ue11_notes.pdf has changed

Binary file ue11.pdf has changed