uebung3
Inhaltsverzeichnis |
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 relativ entscheidbar zur Menge M_2 (M_1,M_2\subseteq A^*), wenn die charakteristische Funktion \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: total berechenbar) Funktion ist. D.h. man kann für jedes 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) entscheidbar, 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) chi gibt, die für jedes Wort w aus A^* nach endlicher Zeit stoppt und entweder #t (w\in M) oder #f (w \not\in M) ausgibt.
> (chi "bin_in_M") #t > (chi "bin_nicht_in_M") #f