\section{Entscheidbarkeit und rekursive Aufzählbarkeit} \inhalta{4-10} \only
{\begin{frame} Wir werden in diesem Abschnitt über den Berechenbarkeitsbegriff für Wort- und Zahlenfunktionen Berechenbarkeitsbegriffe für Mengen einführen. Dann werden wir sehen, dass es auch für die Praxis wichtige Entscheidungsprobleme gibt, die unlösbar sind. Zu einer Teilmenge $A$ von $E^*$ definieren wir zwei Funktionen: \begin{itemize} \item Die charakteristische Funktion $ch_A: E^* \rightarrow \{0,1\}$ ist total und nimmt auf allen Wörtern in $A $ den Wert $1$ an und auf allen Wörtern aus dem Komplement von $A$, also aus $E^*\setminus A$, den Wert $0$: \[ch_A(w):=\left\{\begin{array}{ll} 1,& w\in A\\ 0,&w\not \in A \end{array}\right.\] \item Die eingeschränkte charakteristische Funktion $ch'_A: E^* \Partial \{0,1\}$ ist partiell und nur auf den Wörtern in $A $ definiert. Auf diesen Wörtern nimmt sie den Wert $1$ an. \[ch'_A(w):=\left\{\begin{array}{ll} 1,& w\in A\\ \textrm{undefiniert},&w\not \in A \end{array}\right.\] \end{itemize} \end{frame}} \only{\begin{frame} Betrachte Teilmenge $A\subseteq E^*$: \pause \begin{itemize} \item Die charakteristische Funktion $$ch_A: E^* \rightarrow \{0,1\}$$ ist definiert durch \pause \[ch_A(w):=\left\{\begin{array}{ll} 1,& w\in A \\ \pause 0,&\pause w\not \in A \end{array}\right.\] \item \pause Die eingeschränkte charakteristische Funktion $$ch'_A: E^* \Partial \{0,1\}$$ ist definiert durch \pause \[ch'_A(w):=\left\{\begin{array}{ll} 1,& w\in A \\ \pause\textrm{undefiniert},&\pause w\not \in A \end{array}\right.\] \end{itemize} \pause Wichtig: $ch_A$ ist total; \pause $ch'_A$ ist partiell mit Definitionsbereich $A$ \end{frame}} \begin{frame} \begin{definition} \begin{enumerate} \item Eine Teilmenge $A\subseteq E^*$ hei"st {\bfseries entscheidbar}, \pause wenn ihre charakteristische Funktion $ch_A: E^* \rightarrow \{0,1\}$ {\bfseries berechenbar} ist. \pause \item Eine Teilmenge $A\subseteq E^*$ hei"st {\bfseries semi-entscheidbar}, \pause wenn ihre eingeschränkte charakteristische Funktion $ch'_A: E^* \Partial \{0,1\}$ {\bfseries berechenbar} ist. \end{enumerate} \pause Für Mengen $A\subseteq\nz^k$ werden die Begriffe analog definiert. \pause Der Begriff `$A$ ist unentscheidbar' bedeutet im folgenden das Gleiche wie `$A$ ist nicht entscheidbar'. \end{definition} \only
{ Eine Menge $A $ von Wörtern ist also entscheidbar, wenn es einen Algorithmus (um genau zu sein: eine deterministische Turingmaschine) gibt, der bei Eingabe eines Wortes $w $ nach endlich vielen Schritten anhält und sagt, ob $w $ zur Menge gehört oder nicht. Bei einer semi-entscheidbaren Menge wird weniger verlangt. Da muss es nur einen Algorithmus geben, der sich bei Eingabe eines Wortes $w $ aus $A $ wie folgt verhält: falls $w $ aus $A $ ist, muss er nach endlich vielen Schritten anhalten und verkünden, dass $w $ aus $A $ ist. Falls $w $ nicht aus $A $ ist, liefert er nie eine Antwort. Das Problem dabei ist, dass man von einem Wort, bei dem der Algorithmus zu einem bestimmten Zeitpunkt noch nicht angehalten hat, eben nicht wei"s, ob er nie anhalten wird (dann liegt das Wort nicht in der Menge $A$) oder ob er vielleicht etwas später doch noch anhalten wird (dann liegt das Wort in der Menge $A$). } \only{\pause $A$ ist entscheidbar, \pause wenn ein Algorithmus (d.h. deterministische Turingmaschine) existiert, \pause der bei Eingabe eines beliebigen $w $ anhält \pause und dann sagt, ob $w\in A$ oder $w\not\in A$. \pause $A$ ist semi-entscheidbar, \pause wenn ein Algorithmus mit folgender Eigenschaft existiert: \pause \begin{itemize} \item falls $w\in A $, \pause muss er nach endlich vielen Schritten anhalten \pause\\ und anzeigen, dass $w\in A$ gilt, \pause \item falls $w\not\in A $, \pause so hält der Algorithmus nie an. \end{itemize} } \end{frame} \begin{frame} \only
{ Der Zusammenhang zwischen den beiden Begriffen wird durch den folgenden Satz hergestellt. } \begin{theorem} \pause \label{semi/entscheidbar} Eine Sprache $A$ ist genau dann entscheidbar, \pause wenn sowohl $A$ als auch ihr Komplement $E^*\setminus A $ \pause semi-entscheidbar sind. \end{theorem} \pause Beweis: \only
{ Wenn $A$ entscheidbar ist, ist die charakteristische Funktion $ch_A$ berechenbar. Wenn man eine Maschine, die sie berechnet, so umbaut, dass sie statt $0$ auszugeben, in eine Endlosschleife läuft, so erhält man eine Maschine, die die eingeschränkte charakteristische Funktion $ch'_A$ berechnet. Also ist $A $ dann semi-entscheidbar. Ebenso folgt, dass das Komplement von $A $ semi-entscheidbar ist: dazu muss man eine Maschine, die die charakteristische Funktion $ch_A$ berechnet, so umbauen, dass sie statt $1$ auszugeben in eine Endlosschleife läuft und anstelle von $0$ jeweils $1$ ausgibt. Die Umkehrung folgt durch Kombination von Semi-Entscheidungsalgorithmen für $A$ und Komplement $E^*\setminus A$: man lässt bei Eingabe eines Wortes $w$ eine Maschine, die die eingeschränkte charakteristische Funktion von $A $ berechnet, und eine Maschine, die die eingeschränkte charakteristische Funktion von Komplement $E^*\setminus A$ berechnet, parallel laufen. Genau eine der beiden wird nach endlich vielen Schritten anhalten. Dann wei"s man, ob $w$ in $A $ liegt oder im Komplement von $A $ und kann entsprechend $1$ oder $0$ ausgeben. } \only{ '$\Rightarrow$': \pause Sei $A$ entscheidbar, \pause \\ d.h. $ch_A$ ist berechenbar \pause (mit einer Maschine $M$) \pause Konstruiere $M'$ wie folgt: \pause \begin{itemize} \item Bei Eingabe $w$ berechnet $M'$ zunächst $ch_A(w)$ \pause (mittels $M$) \pause \item Ist das Resultat $1$, \pause so hält $M'$ und akzeptiert $w$ \pause \item Ist das Resultat $0$, \pause so startet $M'$ eine Endloschleife \end{itemize} \pause $\Rightarrow$ $M'$ berechnet $ch'_A$, \pause d.h. $A$ ist semi-entscheidbar \pause Vertausche Rollen von $1$ und $0$ bei $M'$: \pause \\ $\Rightarrow$ $M'$ berechnet jetzt $ch'_{E^*\setminus A}$, \pause d.h. $E^*\setminus A$ ist semi-entscheidbar } \end{frame} \only
{\begin{frame} Die Umkehrung folgt durch Kombination von Semi-Entscheidungsalgorithmen für $A$ und Komplement $E^*\setminus A$: man lässt bei Eingabe eines Wortes $w$ eine Maschine, die die eingeschränkte charakteristische Funktion von $A $ berechnet, und eine Maschine, die die eingeschränkte charakteristische Funktion von Komplement $E^*\setminus A$ berechnet, parallel laufen. Genau eine der beiden wird nach endlich vielen Schritten anhalten. Dann wei"s man, ob $w$ in $A $ liegt oder im Komplement von $A $ und kann entsprechend $1$ oder $0$ ausgeben. \end{frame}} \only{\begin{frame} '$\Leftarrow$': \pause Gegeben Maschinen $M`$, $M''$: \pause\\ $M'$ berechne $ch'_A$, \pause $M''$ berechne $ch'_{E^*\setminus A}$ \pause Konstruiere neue Turingmaschine $M$ wie folgt: \pause \begin{itemize} \item $w$ sei Eingabe für $M$ \pause \item $M$ simuliert abwechselnd \pause einen Rechenschritt von $M'$ auf $w$ \pause\\ und einen Schritt von $M''$ auf $w$ \pause \item Hält $M'$ an, \pause so hält auch $M$ \pause und akzeptiert $w$ \pause \item Hält $M''$ an, \pause so hält auch $M$ \pause und verwirft $w$ \end{itemize} \pause Bei Eingabe von $w$ hält genau eine der Maschine $M'$ und $M''$, \pause d.h. \begin{itemize} \item $M$ hält in jedem Fall an \pause und \item $M$ berechnet $ch_A$ \end{itemize} \end{frame}} \begin{frame} \only
{ Die semi-entscheidbaren Mengen können auch auf andere Weise charakterisiert werden. } \begin{definition} \pause Eine Sprache $A\subseteq E^*$ hei"st rekursiv aufzählbar, \pause falls $A$ leer ist \pause oder Bildbereich einer totalen berechenbaren Funktion $f:\nz\rightarrow E^*$ ist: \pause \[A := \{f(0),f(1),...\}\] \pause Für Teilmengen $A\subseteq\nz^k$ wird der Begriff analog definiert. \pause \end{definition} \begin{theorem} \pause Eine Sprache $A$ aus $E^*$ ist genau dann semi-entscheidbar, \pause \\wenn sie rekursiv aufzählbar ist. \end{theorem} \end{frame} \only
{\begin{frame} Beweis: Sei $A$ rekursiv aufzählbar. Wenn $A $ die leere Menge ist, ist $A $ natürlich auch entscheidbar, denn die charakteristische Funktion der leeren Menge ist die konstante Funktion mit Wert $0$, und die ist berechenbar. Sei $A $ Wertebereich einer totalen berechenbaren Funktion $f :\nz\rightarrow E^*$. Der folgende Algorithmus hält bei Eingabe eines Wortes $w $ genau dann an (und gibt dann $1$ aus), wenn $w$ aus $A$ ist. Also ist $A$ semi-entscheidbar. ~~~~~~~~~~~\texttt{\begin{tabular}{|l|}\hline INPUT($w$); \pause \\ FOR $n= 0, 1, 2, 3,...$ DO \pause \\ ~~~IF $f(n) = w $ THEN OUTPUT($1$) END; \pause \\ END.\\\hline \end{tabular}} \end{frame}} \only{\begin{frame} Beweis: \pause Sei $A$ rekursiv aufzählbar. \pause Fall (1), $A=\emptyset$: \pause \begin{quote} Dann $ch_A(x)=0$ für alle $x$, \pause also $A$ entscheidbar \end{quote} \pause Fall (2), $A=\{f(0),f(1),...\}$ \pause mit totalem berechenbaren $f :\nz\rightarrow E^*$: \pause \begin{quote} Betrachte (berechenbares!) $g$ definiert über \pause ~~~~~~~~~~~\texttt{\begin{tabular}{|l|}\hline INPUT($w$); \\ \pause FOR $n= 0, 1, 2, 3,...$ DO \\ \pause ~~~IF $f(n) = w $ THEN OUTPUT($1$) END; \\ \pause END.\\\hline \end{tabular}} \pause $w\in A$ $\Rightarrow$ \pause $g(w)=1$ \pause \\ $w\not\in A$ $\Rightarrow$ \pause $g(w)$ undefiniert \pause $\Longrightarrow$ $A$ semi-entscheidbar \end{quote} \end{frame}} \only
{\begin{frame} Sei nun $A $ semi-entscheidbar und nicht leer; $M$ sei eine Turingmaschine, die $ch_A'$ berechnet. Wir müssen zeigen, dass es eine totale berechenbare Funktion $f:\nz\rightarrow E^*$ mit $A := \{f(0), f(1),...\}$ gibt. Dazu wählen wir zuerst irgendein Element $a\in A$. Der folgende Algorithmus berechnet eine derartige Funktion $f$. \texttt{\begin{tabular}{ll} INPUT($n$); \\ $k:= p_1(n); l:= p_2(n); w := \nu(k);$\\ IF \textrm{ Angesetzt auf $w$ stoppt $M$ }\\ ~~~~~~~ \textrm{ nach höchstens $l$ Schritten mit Ausgabe von $1$} \\ THEN OUTPUT($w$) ELSE OUTPUT($a$) \\ END. \end{tabular}} In dem Algorithmus verwenden wir die beiden LOOP-berechenbaren Funktionen $p_1$ und $p_2$, also die Umkehrfunktionen zu der Cantorschen Bijektion $c$ zwischen $\nz^2$ und $\nz$ aus Abschnitt \ref{CantorLOOP} Das hei"st, wir interpretieren $n$ als Codierung zweier Zahlen $k$ und $l$. Au"serdem interpretieren wir die Zahl $k$ mittels der Bijektion $\nu$ zwischen $\nz$ und $E^*$ aus Abschnitt \ref{Wort-Zahl} als Wort $w\in E^*$. Wir testen also mit dem Algorithmus für alle möglichen Wörter $w\in E^*$ und alle möglichen Laufzeiten $l$, ob die Maschine $M$ bei Eingabe von $w$ nach $l$ Schritten anhält. Falls ja, geben wir $w$ aus, sonst das Wort $a$, das ja sicher in $A$ liegt. Der Algorithmus hält also immer an und gibt nur Wörter aus $A$ aus (möglicherweise mit Wiederholungen). Da es aber andererseits zu jedem $w $ aus $A$ eine Schrittzahl $l$ gibt, nach der $M$ mit Ausgabe $1$ anhält, gibt der Algorithmus bei Eingabe von $n = c(\nu^{-1}(w), l)$ dann $w$ aus. Also ist $A$ der Wertebereich von $f$. Man nennt dieses Verfahren oft \emph{dove-tailing}. \end{frame}} \only{\begin{frame} Sei nun $A $ semi-entscheidbar, \pause $A\neq\emptyset$ \pause \begin{itemize} \item $M$ sei eine Turingmaschine, die $ch_A'$ berechnet. \pause \item $a$ sei beliebig gewähltes Element von $A$. \end{itemize} \pause Betrachte (berechenbares!) $g$ definiert über \pause ~~~~\texttt{\begin{tabular}{|l|}\hline INPUT($n$); \\ \pause $k:= p_1(n); \pause l:= p_2(n); \pause w := \nu(k);$ \\ \pause IF \textrm{ Angesetzt auf $w$ stoppt $M$ }\\ \pause ~~~~~~~ \textrm{ nach höchstens $l$ Schritten mit Ausgabe von $1$} \\ \pause THEN \pause OUTPUT($w$) \pause ELSE OUTPUT($a$)\\ \pause END.\\\hline \end{tabular}} \end{frame}} \only{\begin{frame} \begin{itemize} \item $p_1$, $p_2$: LOOP-berechenbare Umkehrfunktionen \\ der Cantorschen Bijektion $c$ zwischen $\nz^2$ und $\nz$ \pause \item $n$ codiert (bijektiv!) zwei Zahlen $k$ und $l$ \pause \item $k$ codiert (bijektiv!) Worte $w$ \end{itemize} \pause $\Longrightarrow$ Algorithmus testet \pause \begin{itemize} \item für alle möglichen Wörter $w\in E^*$ \pause und \item für alle möglichen Laufzeiten $l$, \pause \item ob $M$ bei Eingabe von $w$ nach $l$ Schritten anhält. \end{itemize} \pause \begin{enumerate} \item Die berechnete Funktion $g$ ist total \pause \item Stets gilt $g(n)\in A$ \pause \item Für jedes $w\in A$ hält $M$ \pause nach $l_w$ Schritten für ein $l_w\in\nz$, \pause \\ d.h. $g(n_w)=w$ für $n_w$ \pause mit $p_2(n_w)=l_w$ \pause und $\nu p_1(n_w)=w$ \end{enumerate} \pause Damit $A=\{ g(n)\mid n\in\nz\}$ \pause Bezeichnung der Verfahrenweise: \Fb{dove-tailing}. \end{frame}} \begin{frame} \only
{ Die bisherigen Sätze gelten für Teilmengen von $\nz$ oder von $\nz^k$ natürlich ebenso wie für Sprachen. Damit sind die folgenden Aussagen äquivalent: } \only{ Statt $A\subseteq E^*$ ist auch $A\subseteq \nz^k$ möglich, \pause damit: } \begin{block}{} Für $A\subseteq E^*$ sind folgende Aussagen äquivalent: \pause \Fb{\begin{itemize} \item $A$ ist Sprache vom Typ 0\pause \item $A $ wird von einer nichtdeterministischen Turingmaschine erkannt\pause \item $A $ wird von einer deterministischen Turingmaschine erkannt\pause \item Es gibt eine deterministische Turingmaschine, die bei Eingabe eines Wortes $w\in E^*$ genau dann nach endlich vielen Schritten anhält, wenn $w\in A $ ist\pause \item $A$ ist semi-entscheidbar, d.h. die eingeschränkte charakteristische Funktion $ch'_A$ ist berechenbar\pause \item $A$ ist Definitionsbereich einer berechenbaren Funktion\pause \item $A$ ist rekursiv aufzählbar\pause \item $A$ ist leer oder Wertebereich einer totalen berechenbaren Funktion \end{itemize}} \pause Äquivalent dazu ist auch \Fb{\begin{itemize} \item $A $ ist Wertebereich einer (partiellen) berechenbaren Funktion \end{itemize}}\end{block} \only{\vspace{-.6ex}} \pause (Beweis der noch nicht bewiesenen Äquivalenzen als Übung...) \end{frame} \begin{frame} \only
{ Wir werden nun zeigen, dass es rekursiv aufzählbare Mengen gibt, die nicht entscheidbar sind. Dafür kommen wir auf die Notation von Turingmaschinen und berechenbaren Wortfunktionen aus \ref{h-Notation} zurück. Wir hatten Turingmaschinen und damit auch berechenbare Wortfunktionen durch Wörter über dem Binäralphabet $\{0, 1\}$ codiert. Ist $w $ ein Binärwort, so sei $M_w$ die wie in \ref{h-Notation} durch $w $ bezeichnete Turingmaschine und $h_w$ die von $M_w$ berechnete Wortfunktion. } \only{ \begin{itemize} \item Sei $h$ die Notation der berechenbaren Wortfunktionen aus \ref{h-Notation} \pause \item $M_w$ sei die durch $w\in\{0,1\}^*$ bezeichnete Turingmaschine \pause \item $h_w$ sei die durch $w\in\{0,1\}^*$ berechnete Wortfunktion \pause \end{itemize} } \begin{definition} Das \Fb{spezielle Halteproblem} \pause oder \Fb{Selbstanwendbarkeitsproblem} \pause ist die Menge \GLA K &:= &\pause \{ w\in\{0, 1\}^* \pause \mid M_w\textrm{ angesetzt auf }w \\ &&\pause ~~~~~~~~~~~~\textrm{ hält nach endlich vielen Schritten an}\} \\[1ex] &\pause =&\pause \{ w\in \{0, 1\}^* \pause \mid h_w(w) \pause \textrm{ ist definiert }\} \GLE \end{definition} \pause \begin{theorem} \pause Das spezielle Halteproblem $K$ ist rekursiv aufzählbar,\pause\\ aber nicht entscheidbar.\label{Halteproblem} \end{theorem} \end{frame} \only
{\begin{frame} Dass die Menge $K $ rekursiv aufzählbar ist, liegt an der utm-Eigenschaft der Notation $h $ für die berechenbaren Wortfunktionen. Wir geben noch einmal die Begründung: Ist $w $ gegeben, so kann man daraus effektiv das Aussehen von $M_w$ ablesen. Daher gibt es eine Turingmaschine, die bei Eingabe von $w $ die Maschine $M_w$, angesetzt auf $w$, simuliert und genau dann anhält, wenn $M_w$, angesetzt auf $w$, anhält. Wäre die Menge $K $ entscheidbar, so wäre nach Satz \ref{semi/entscheidbar} auch ihr Komplement, also die Menge $E^*\setminus K$, semi-entscheidbar. Dann gäbe es also eine Turingmaschine $TM$, die, angesetzt auf ein beliebiges Binärwort $w$ genau dann nach endlich vielen Schritten anhält, wenn $w$ nicht aus $K$ ist. Sei $x$ ein Codewort für so eine Maschine, d.h. $M_x$ sei so eine Maschine. Wir setzen diese Maschine auf ihr eigenes Codewort $x$ an und beobachten: \begin{itemize} \item Wenn $M_x$ angesetzt auf $x$ nach endlich vielen Schritten anhält, dann gilt nach Definition von $M_x$, dass $x\not\in K $ ist. Aber nach Definition von $K $ darf dann $M_x$ angesetzt auf $x $ niemals anhalten. Widerspruch! \item Wenn $M_x$ angesetzt auf $x $ nicht nach endlich vielen Schritten anhält, dann gilt nach Definition von $M_x$, dass $x\in K $ ist. Aber nach Definition von $K$ muss dann $M_x$ angesetzt auf $x$ doch nach endlich vielen Schritten anhalten. Widerspruch! \end{itemize} In beiden Fällen erhalten wir einen Widerspruch. Also war die Annahme falsch, und $K $ ist nicht entscheidbar. \end{frame}} \only{\begin{frame} $K$ ist rekursiv aufzählbar: \pause \begin{itemize} \item $g(w\#v):=h_w(v)$ ist berechenbar (utm-Eigenschaft) \pause \item also auch $f$ mit $f(w):= \pause g(w\#w) \pause =h_w(w)$ \pause \item $w\in K\Leftrightarrow f(w) $ definiert \end{itemize} \pause Annahme: $K$ sei entscheidbar. \pause \begin{itemize} \item Dann insbesondere $E^*\setminus K$ semi-entscheidbar \pause \item Sei $TM$ eine Turingmaschine, die genau dann auf $w$ hält, \pause\\ wenn $w\in E^*\setminus K$ \pause \item Sei $x$ ein Codewort für $TM$, \pause d.h. \[h_x(w)\textrm{ ist definiert }\Leftrightarrow \pause w\in E^*\setminus K\] \only{\vspace{-.6ex}} \end{itemize} \pause Betrachte $h_x(x)$: \pause \GLA x\in K&\Leftrightarrow &\pause TM\textrm{ hält nicht auf }x\\ &\pause \Leftrightarrow &\pause h_x(x)\textrm{ nicht definiert}\\ &\pause \Leftrightarrow &\pause x\not\in K \pause \textrm{ (Widerspruch...)}\GLE \pause Also war die Annahme falsch, \pause und $K $ ist \emph{nicht} entscheidbar. \end{frame}} \begin{frame} \only
{ Die hier verwendete Diagonalisierung kann mit der ähnlich gelagerten Diagonalisierung aus dem Kapitel über LOOP-Berechenbarkeit verglichen werden: Wieder werden alle ``Programme'' aufgelistet und an der Diagonale ein Widerspruch erzeugt: \[\begin{array}{|c|c|c|c|c|c} \hline & 0 & 1 & 2 & 3&\cdots \\ \hline M_{w_0} & \Fb{h_{w_0}(w_0)} & h_{w_0}(w_1) & h_{w_0}(w_2) & h_{w_0}(w_3) \\ \hline M_{w_1} & h_{w_1}(w_0) & \Fb{h_{w_1}(w_1)} & h_{w_1}(w_2) &h_{w_1}(w_3) \\ \hline M_{w_2} & h_{w_2}(w_0) & h_{w_2}(w_1) & \Fb{h_{w_2}(w_2)} & h_{w_2}(w_3) \\ \hline M_{w_3} & h_{w_3}(w_0) & h_{w_3}(w_1) & h_{w_3}(w_2) & \Fb{h_{w_3}(w_3)} \\ \hline \vdots&&&&& \end{array}\] Allerdings wird hier nur betrachtet, ob das Resultat definiert ist, also z.B. \[\begin{array}{|c|c|c|c|c|c} \hline & 0 & 1 & 2 & 3&\cdots \\ \hline M_{w_0} & \Fb{def}~ & ? & ? & ? \\ \hline M_{w_1} & ? & \Fb{udef} & ? &? \\ \hline M_{w_2} & ? & ? & \Fb{udef} & ? \\ \hline M_{w_3} & ? & ? & ? & \Fb{def}~ \\ \hline \vdots&&&&& \\ \hline \hline K & \in & \not\in & \not\in & \in \\ \hline E^*\setminus K & \not\in & \in & \in & \not\in \\ \hline \end{array}\] Damit passt $E^*\setminus K$ zu keiner der Zeilen darüber. } \only{zugrundeliegende Beweisidee: Alle ``Programme'' listen und an der Diagonale Widerspruch einbauen: {\small \[\begin{array}{|c|c|c|c|c|c} \hline ~~~~~~~~~~~ &~~~~~~~ 0 ~~~~~~~& ~~~~~~~1 ~~~~~~~&~~~~~~~ 2~~~~~~~ &~~~~~~~ 3~~~~~~~&\cdots \\ \hline M_{w_0} & \Fb{h_{w_0}(w_0)} & h_{w_0}(w_1) & h_{w_0}(w_2) & h_{w_0}(w_3)&\cdots \\ \hline M_{w_1} & h_{w_1}(w_0) & \Fb{h_{w_1}(w_1)} & h_{w_1}(w_2) &h_{w_1}(w_3)&\cdots \\ \hline M_{w_2} & h_{w_2}(w_0) & h_{w_2}(w_1) & \Fb{h_{w_2}(w_2)} & h_{w_2}(w_3)&\cdots \\ \hline M_{w_3} & h_{w_3}(w_0) & h_{w_3}(w_1) & h_{w_3}(w_2) & \Fb{h_{w_3}(w_3)}&\cdots \\ \hline \vdots&\vdots&\vdots&\vdots&\vdots& \end{array}\]} \pause Betrachte nur, ob das Resultat definiert ist (wg. rek.-aufzählbar):\pause {\small \[\begin{array}{|c|c|c|c|c|c} \hline ~~~~~~~~~~~&~~~~~~~ 0~~~~~~~ &~~~~~~~ 1~~~~~~~ & ~~~~~~~2 ~~~~~~~& ~~~~~~~3~~~~~~~&\cdots \\ \hline M_{w_0} & \Fb{def}~ & ? & ? & ?&\cdots \\ \hline M_{w_1} & ? & \Fa{udef} & ? &?&\cdots \\ \hline M_{w_2} & ? & ? & \Fa{udef} & ?&\cdots \\ \hline M_{w_3} & ? & ? & ? & \Fb{def}~&\cdots \\ \hline \vdots&\vdots&\vdots&\vdots&\vdots& \\ \hline \hline \pause K &\pause \Fb{\in} &\pause \Fa{\not\in} &\pause \Fa{\not\in} &\pause \Fb{\in} \\ \hline \pause E^*\setminus K &\pause \Fa{\not\in} &\pause \Fb{\in} &\pause \Fb{\in} &\pause \Fa{\not\in} \\ \hline \end{array}\]} Damit passt $E^*\setminus K$ zu keiner der Zeilen darüber. } \end{frame} \begin{frame} \begin{remark} \only
{ Im Beweis haben wir lediglich die utm-Eigenschaft der Programmiersprache $h $ benutzt, und die auch nur zum Nachweis der rekursiven Aufzählbarkeit. Man kann den Satz daher direkt auf andere Notationen für die berechenbaren Wortfunktionen übertragen. Das hei"st, ist $h'$ irgendeine Notation für die berechenbaren Wortfunktionen, die die utm-Eigenschaft hat, so ist die Menge \[K = \{w\in\{0, 1\}^*\mid h'_w(w)\textrm{ ist definiert}\}\] rekursiv aufzählbar, aber nicht entscheidbar. Das hei"st, es gibt keine Notation für die berechenbaren Wortfunktionen, die die utm-Eigenschaft hat und die Eigenschaft, dass man bei Eingabe eines Programms entscheiden kann, ob es auf sich selbst angesetzt je anhält. } \only{ nur utm-Eigenschaft der Programmiersprache $h$ notwendig: \pause \begin{quote} Ist $h'$ eine Notation für die berechenbaren Wortfunktionen mit der utm-Eigenschaft, \pause so ist die Menge \[K = \{w\in\{0, 1\}^*\mid h'_w(w)\textrm{ ist definiert}\}\] \pause rekursiv aufzählbar, aber nicht entscheidbar. \end{quote}} \end{remark} \end{frame} \begin{frame} \only
{ Die Unlösbarkeit des speziellen Halteproblems mag nicht besonders wichtig erscheinen. Aber ausgehend von diesem Problem kann man auch von anderen Problemen zeigen, dass sie nicht entscheidbar sind. Eine ganze Klasse von nicht entscheidbaren Sprachen oder Mengen kann man über das folgende Reduktionslemma erschlie"sen: } \begin{definition} \pause Seien $A, B\subseteq E^*$ Sprachen. \pause \label{Reduzierbarkeit} Dann hei"st $A$ auf $B$ reduzierbar (`$A\leq B$'), \pause wenn es eine totale berechenbare Funktion $f: E^* \rightarrow E^*$ gibt, \pause so dass für alle $x\in E^*$ gilt \pause \GLA x\in A\Longleftrightarrow f(x)\in B \GLE \end{definition} \only{\pause \begin{itemize} \item $A\leq B$: Lösung von Problem $A$ durch Lösung von Problem $B$ (daher: $A$ auf $B$ `reduziert')\pause \item $B$ ist in der Regel `schwerer' lösbar als $A$, aber evtl. `Lösung' für $B$ schon bekannt.... \end{itemize} \pause } \only
{Die Grundidee dabei ist, dass wir bei $A\leq B$ das Problem $A$ durch das Problem $B$ lösen können (daher: `$A$ auf $B$ reduziert'). Allerdings ist $B$ in der Regel ein schwereres Problem als $A$, aber eventuell ist die `Lösung' für $B$ ja schon bekannt.... Es folgt sofort:} \begin{theorem} \pause Sei die Sprache $A$ auf $B$ mittels der Funktion $f $ reduzierbar. \label{Reduktion}\pause Dann gilt: \begin{itemize} \item Ist $B$ entscheidbar, so ist auch $A$ entscheidbar. \pause \item Ist $A$ nicht entscheidbar, so ist auch $B$ nicht entscheidbar. \pause \item Ist $B$ rekursiv-aufzählbar, so ist auch $A$ rekursiv-aufzählbar. \pause \item Ist $A$ nicht rek.-aufzählbar, so ist auch $B$ nicht rek.-aufzählbar. \end{itemize} \end{theorem} \end{frame} \only
{\begin{frame} Beweis: \\ Wir wollen annehmen, dass die charakteristische Funktion $ch_B$ von $B$ berechenbar ist. Dann ist auch die Kompositionsfunktion $ch_B\circ f$ berechenbar. Es gilt aber: \[ch_A(x) = 1 \Longleftrightarrow x \in A\Longleftrightarrow f(x)\in B \Longleftrightarrow ch_B(f(x)) = 1\] Analog gilt \[ch_A(x) = 0 \Longleftrightarrow x\not\in A \Longleftrightarrow f(x) \not\in B \Longleftrightarrow ch_B(f(x)) = 0\] Im Fall der Semi-Entscheidbarkeit ersetzt man $ch$ durch $ch'$ und beachtet, dass $ch'$ im Fall der Nichtzugehörigkeit undefiniert ist. \end{frame}} \only{\begin{frame} Beweis: $f$ sei berechenbar und reduziere $A$ auf $B$ \pause (a) $B$ sei entscheidbar. \pause Dann $ch_B$ berechenbar, \pause Komposition $ch_B\circ f$ berechenbar \pause und \GLA ch_A(x) = 1 &\Longleftrightarrow &\pause x \in A\Longleftrightarrow \pause f(x)\in B \pause \Longleftrightarrow ch_B(f(x)) = 1 \\ ch_A(x) = 0 &\Longleftrightarrow &\pause x\not\in A \Longleftrightarrow \pause f(x) \not\in B \Longleftrightarrow \pause ch_B(f(x)) = 0 \GLE \pause Also $ch_A=ch_B\circ f$ berechenbar, \pause und $A$ entscheidbar \pause (b) $B$ sei rekursiv-aufzählbar \pause Dann: $ch'_B$ berechenbar, \pause Komposition $ch'_B\circ f$ berechenbar \pause und \[\begin{array}{@{}r@{}l@{}} ch'_A(x) = 1&\Longleftrightarrow \pause x \in A\Longleftrightarrow f(x)\in B \pause \Longleftrightarrow ch'_B(f(x)) = 1 \\ \pause ch'_A(x) = \text{undef.}&\Longleftrightarrow \pause x\not\in A \Longleftrightarrow \pause f(x) \not\in B \Longleftrightarrow \pause ch'_B(f(x)) = \text{undef.} \end{array}\] \pause Also $ch'_A=ch'_B\circ f$ berechenbar, \pause und $A$ rekursiv-aufzählbar \end{frame}} \begin{frame} \pause \begin{definition} Das \Fb{allgemeine Halteproblem} \pause ist die Sprache \[ H = \{~~w\$x\in \{0, 1\}^*\{\$\}E^*~~ \pause \mid M_w\textrm{ angesetzt auf }x\textrm{ hält an}\}\] \pause Dabei sei $\$$ irgendein Symbol, das in $E$ nicht vorkommt. \end{definition} \pause \begin{theorem} \pause Das allgemeine Halteproblem ist rekursiv aufzählbar, \pause aber nicht entscheidbar. \end{theorem} \pause Beweis: \pause \only
{ Dass $H $ semi-entscheidbar und daher auch rekursiv aufzählbar ist, folgt wieder aus der utm-Eigenschaft. Zum Beweis der Nicht-Entscheidbarkeit reduzieren wir $K $ auf $H$. Dies geschieht mit der totalen und sicherlich berechenbaren Abbildung $f $ definiert durch $f(w) = w\$w$.} \only{ $H$ semi-entscheidbar / rekursiv aufzählbar: \pause sofort mit utm-Eigenschaft \pause $H$ unentscheidbar: \pause $K$ ist auf $H$ reduzierbar \pause mit folgendem $f$ \pause $$f(w) := w\$w$$ \pause $f$ ist sicherlich total und berechenbar. } \end{frame} \begin{frame} \only
{ Der folgende Satz von Rice wird auch über die Reduktionsmethode bewiesen. Er liefert eine gro"se Klasse von nichtentscheidbaren Problemen.} \begin{theorem}[Rice] \pause Sei $R$ die Klasse aller Turing-berechenbaren Wortfunktionen über dem Alphabet $E$.\pause Sei $S$ eine echte, nichttriviale Teilmenge von $R$, \pause d.h. $\emptyset\neq S\pause\neq R$ \pause Dann ist die folgende Sprache unentscheidbar: \pause \[C(S) = \{w\in\{0,1\}^* \pause | \textrm{ die von }M_w\textrm{ berechnete Funktion }h_w\textrm{ liegt in }S \}\] \end{theorem} \pause Beweis: \pause Sei $S$ mit $\emptyset\neq S\neq R$ gegeben, \pause sei $ud$ die überall undefinierte (berechenbare!) Funktion. \pause Also $ud\in S$ oder $ud\not\in S$. \pause Wir behandeln diese beiden Fälle getrennt. \end{frame} \begin{frame} (a)\only
{ Nehmen wir an, dass $ud$ aus $S$ ist. Da nach Voraussetzung $S\neq R$, gibt es eine Funktion $q$ aus dem Komplement von $S$ und eine sie berechnende Turingmaschine $Q$. Wir betrachten die Turingmaschine $TM$, die sich wie folgt verhalte: } \only{Sei $ud\in S$. \pause Wegen $S\neq R$ gibt es $q\in R\setminus S$ \pause Sei $Q$ eine Turingmaschine für $q$. \pause Betrachte folgende Turingmaschine $TM$: \pause } \begin{quote} Bei Eingabe von $w\#x$ \pause simuliert $TM$ erst die Maschine $M_w$ \pause angesetzt auf $w$. \pause Kommt diese Rechnung zu einem Ende, \pause so soll $TM$ anschlie"send $Q$ angesetzt auf $x$ simulieren. \end{quote} \pause $g$ sei die von $TM$ berechnete Funktion. \pause Mit der smn-Eigenschaft von $h$ gibt es ein totales berechenbares $r: \{0,1\}^* \rightarrow \{0,1\}^*$ \pause mit $g(w\#x)=h_{r(w)}(x)$ \pause Damit gilt: \pause \begin{itemize} \item Hält $M_w$ auf $w$, \pause so ist $h_{r(w)}=q$. \pause \item Hält $M_w$ nicht auf $w$, \pause so ist $h_{r(w)}=ud$ \end{itemize} \end{frame} \begin{frame} Dann gilt: \pause \begin{tabular}{lll} $w\in K$ &$\Rightarrow $ &\pause Angesetzt auf $w $ stoppt $M_w$ \\ &\pause $\Rightarrow$ &\pause $h_{r(w)}$ ist die Funktion $q$\\ &\pause $\Rightarrow$ &\pause $h_{r(w)}$ liegt nicht in $S$\\ &\pause $\Rightarrow$ &\pause $r(w) \not\in C(S)$. \end{tabular} \pause sowie \begin{tabular}{lll} $w\not\in K$ &$\Rightarrow$ &\pause Angesetzt auf $w$ stoppt $M_w$ nicht \\ &\pause $\Rightarrow$ &\pause $h_{r(w)}$ ist die Funktion $ud$ \\ &\pause $\Rightarrow$ &\pause $h_{r(w)}$ liegt in $S$\\ &\pause $\Rightarrow$ &\pause $r(w)\in C(S)$. \end{tabular} \only
{ Damit vermittelt $r$ eine Reduktion vom Komplement von $K$ auf $C(S)$, was für unseren Zweck ausreicht, da auch das Komplement von $K$ unentscheidbar ist.} \only{ \pause Also: $r$ reduziert $E^*\setminus K$ auf $C(S)$, \pause d.h $C(S)$ nicht entscheidbar \pause } (b) \only
{Ist $ud$ nicht aus $S$, so zeigt man analog: Es existiert eine berechenbare Funktion, die eine Reduktion von $K $ nach $C(S)$ vermittelt.} \only{Analog: \pause Reduktion von $K$ auf $C(S)$, \pause d.h. $C(S)$ nicht entscheidbar} \end{frame}\begin{frame} \begin{remark}\only
{~\newline} (1) Der Beweis des Satzes von Rice nutzt nur die utm-Eigenschaft und die smn-Eigenschaft von $h$. \pause Eine andere Formulierung ist daher: \pause \begin{quote}Ist $h'$ Notation der berechenbaren Wortfunktionen \pause mit utm-Eigenschaft und smn-Eigenschaft, dann gilt: \pause Für jede Teilmenge $S$ von $R$ mit $\emptyset\neq S\neq R$ \pause ist die Menge \[C(S)=\{w\in \{0,1\}^* | h'_w \textrm{ liegt in }S\}\] \pause nicht entscheidbar. \end{quote} \end{remark} \end{frame}\begin{frame} \begin{cont}{} (2) Anwendungsbeispiele: \pause \begin{itemize} \item $S_1=\{ f \textrm{ berechenbar und total }\}$\pause Man kann bei (realen) Programmen i.d.R. nicht entscheiden, \pause \\ ob sie immer halten. \pause \item $S_2=\{ g\}\textrm{ für ein gegebenes }g$ \pause Man kann bei (realen) Programmen i.d.R. nicht entscheiden, \pause \\ ob sie eine exakt vorgegebene Funktion berechnen \pause \item $S_3=\{ g\mid g(\varepsilon)=\varepsilon\}$ \pause Man kann bei (realen) Programmen i.d.R. nicht entscheiden, \pause \\ ob sie eine vorgegebene Spezifikation erfüllen \pause (hier: $g(\varepsilon)=\varepsilon$) \end{itemize} \pause Die Beispiele zeigen, dass zum Beispiel Verifikation von Software schwierig ist, sobald die Programmiersprache 'vernünftig' ist (d.h. alle berechenbaren Funktionen umfasst und utm/smn-Eigenschaften hat). \end{cont} \end{frame} \begin{frame} Es gibt Probleme, die `noch unlösbarer' als das spezielle oder allgemeine Halteproblem sind. \pause Dazu gehört das \Fb{\"Aquivalenzproblem für Turingmaschinen}: \pause \GLA A &=& \{ v\$w\mid \textrm{ die Turingmaschinen }M_v\textrm{ und } M_w\\&&~~~~~~~~~~~~~~\textrm{ berechnen dieselbe Funktion}\}\GLE \pause Man kann zwar $K$ auf $A$ reduzieren, aber $A$ nicht auf $K$.\\ \pause Darauf aufbauend kann man ganze Hierarchien im Grad der Unlösbarkeit schwieriger werdender Probleme aufbauen. \end{frame}