BuK/IIm12/Studenten/sifedeut/uebung3
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
=Theorie=
Im Gegensatz zu Funktionen sind Mengen nicht ''berechenbar'', sondern ''entscheidbar''. Man spricht bei '''Mengen''' von '''Entscheidbarkeit'''
==relativ entscheidbare Mengen==
Eine Menge $M_1$ ist <b>relativ entscheidbar</b> zur Menge $M_2 (M_1,M_2\subseteq A^*)$, wenn die <b>charakteristische Funktion</b> $\chi_{M_1,M_2}$ mit
$\chi_{M_1,M_2}(w)=\begin{cases}wahr & \text{,wenn } w\in M_1\\falsch & \text{, wenn } w\in M_2\setminus M_1\end{cases}$
eine totale und berechenbare (kurz: <b>total berechenbar</b>) Funktion ist. D.h. man kann für <u>jedes</u> Element der Menge $M_2$ sagen, ob es sich um ein Element der Menge $M_1$ handelt oder nicht.
==(absolut) entscheidbare Mengen==
Eine Menge $M\subseteq A^*$ ist (absolut) <b>entscheidbar</b>, wenn $M$ zu $A^*$ relativ entscheidbar ist, d.h. wenn $\chi_{M,A^*}$, kurz $\chi_{M}$, mit
$\chi_{M}(w)=\begin{cases}wahr & \text{,wenn } w\in M\\falsch & \text{, wenn } w\in A^*\setminus M\end{cases}$
eine total berechenbare Funktion ist.
Anders gesagt: $M$ ist entscheidbar, wenn es eine Prozedur (eine in einer beliebigen Programmiersprache implementierte Funktion) <tt>chi</tt> gibt, die für jedes Wort $w$ aus $A^*$ nach endlicher Zeit stoppt und entweder <tt>#t</tt> ($w\in M$) oder <tt>#f</tt> ($w \not\in M$) ausgibt.
<nowiki>
> (chi "bin_in_M")
#t
> (chi "bin_nicht_in_M")
#f</nowiki>
=Übungsaufgaben zur Entscheidbarkeit und Aufzählbarkeit=