\chapter{Satz von Rice}

\section{Erklärung}
Das nächste Resultat zeigt, dass es unentscheidbar ist, ob die
Funktion, die von einer Turingmaschine $ ~ M ~ $ berechnet wird, eine
bestimmte Eigenschaft $ ~ S ~ $ hat.\\
Das bedeutet, es gibt keine Methode, mit der man für alle
Turingmaschinen verläßliche Aussagen über die von ihnen
berechneten Funktionen machen kann.

\section{Definition}
Sei $ ~ R ~ $ die Klasse aller Turing-berechenbaren Funktionen und sei $ ~ S ~ $
eine beliebige Teilmenge hiervon (mit Ausnahme von $ ~ S = \emptyset ~ $ und
$ ~ S = R ~ $).\\

Dann ist die Sprache:\\
$ C(S) = \{ w ~ | ~ \textnormal{die von} ~ M_{w} ~ \textnormal{berechnete Funktion liegt in} ~ S \} $ \\

unentscheidbar. Daraus folgt direkt die Unentscheidbarkeit von folgenden \hyperref[svr_probleme]{Problemen}.

\section{Konsequenz des Satzes von Rice}
Kein Programm kann automatisch die Korrektheit von Software überprüfen.
$ \rightarrow $ Testen \\
$ \rightarrow $ Verifikation/Theorembeweiser

\newpage

\section{Beweis für die überall undefinierte Funktion}

\begin{figure}[h]
\centering
\includegraphics[scale=0.45]{imgs/svr_beispiel_1.PNG}
\caption{Sprachtypen}
\end{figure}

\begin{figure}[h]
\centering
\includegraphics[scale=0.45]{imgs/svr_beispiel_2.PNG}
\caption{Sprachtypen}
\end{figure}

\newpage

\section{Ausführliche Erklärung}

Sei $~S~$ eine \textit{semantische}, \textit{nicht-triviale} Eigenschaft von det. TMs. \\
Dann ist das Problem: \\
$ C(S) = \{ w ~ | ~ \textnormal{die von} ~ M_{w} ~ \textnormal{berechnete Funktion liegt in} ~ S \} $ \\
\textbf{unentscheidbar}.\\

\subsection{Was ist eine semantische Eigenschaft?}
Eigenschaft einer det. TM M, die nur von L(TM) abhängt. \\
Wenn L(TM) = L(TM'), dann: \\
Entweder M und M' erfüllen es beide, oder keiner erfüllt es. \\

Semantisch: \\
\begin{itemize}

\item Ist L(TM) regulär?

\item Ist L(TM) = $ ~ \emptyset ~ $ ?

\item Akzeptiert TM mind. n Worte?

\item Ist L(TM) turing-erkennbar?

\item Ist L(TM) überabzählbar unendlich?

\end{itemize}

Nicht semantisch: \\
\begin{itemize}

\item Hat TM min. n Zustände?

\item Hält TM auf Eingabe $ ~ \epsilon ~ $ an?

\item Überschreibt TM bei Eingabe abc jemals ein $ ~ \square $ ?

\end{itemize}

\section{Was ist eine triviale Eigenschaft?}

Eine Eigenschaft, die entweder von jeder det. TM erfüllt oder von gar keiner. \\

\begin{itemize}

\item Ist L(TM) regulär?

\item Ist L(TM) = $ ~ \emptyset ~ $ ?

\item Akzeptiert TM mind. n Worte?

\end{itemize}

Bleiben dann übrig und fallen unter den Satz von Rice.