\section{Entscheidbarkeit und rekursive Aufzählbarkeit}
\inhalta{4-10}


\only<article>{\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<presentation>{\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<article>{
 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<presentation>{\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<article>{
 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<article>{
 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<presentation>{
'$\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<article>{\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<presentation>{\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<article>{
 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<article>{\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<presentation>{\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<article>{\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<presentation>{\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<presentation>{\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<article>{ 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<presentation>{
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<presentation>{\vspace{-.6ex}}
 \pause (Beweis der noch nicht bewiesenen Äquivalenzen als Übung...)
\end{frame}




\begin{frame}
\only<article>{
 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<presentation>{
\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<article>{\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<presentation>{\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<presentation>{\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<article>{
 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<presentation>{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<article>{
 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<presentation>{
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<article>{
 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<presentation>{\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<article>{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<article>{\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<presentation>{\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<article>{
 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<presentation>{
$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<article>{ 
 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<article>{ 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<presentation>{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<article>{ 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<presentation>{
 \pause Also: $r$ reduziert $E^*\setminus K$ auf $C(S)$,  \pause d.h $C(S)$ nicht entscheidbar \pause 
}

 (b) \only<article>{Ist $ud$ nicht aus $S$, so zeigt man analog: 
 Es existiert eine berechenbare Funktion, die eine Reduktion von $K $
nach $C(S)$ vermittelt.}
\only<presentation>{Analog:  \pause Reduktion von $K$ auf $C(S)$,  \pause d.h. $C(S)$ nicht entscheidbar}


 
 
\end{frame}\begin{frame}

\begin{remark}\only<article>{~\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}
