# HG changeset patch # User Markus Kaiser # Date 1404501510 -7200 # Node ID 24d446e2f94c3dd494ea336f16731ec8f5f674bc # Parent 77756390412069223290368883bec0e7bf5f501d eleventh sheet and notes diff -r 777563904120 -r 24d446e2f94c notes/complete_notes.pdf Binary file notes/complete_notes.pdf has changed diff -r 777563904120 -r 24d446e2f94c notes/tex/complete_notes.tex --- 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} diff -r 777563904120 -r 24d446e2f94c notes/tex/computation.tex --- 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} } diff -r 777563904120 -r 24d446e2f94c notes/tex/ue11_notes.tex --- /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} diff -r 777563904120 -r 24d446e2f94c notes/ue11_notes.pdf Binary file notes/ue11_notes.pdf has changed diff -r 777563904120 -r 24d446e2f94c ue11.pdf Binary file ue11.pdf has changed