BuK/IIm12/Studenten/sifedeut/uebung3

Wiki-Quelltext dieser Seite.

=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.

=Übungsaufgaben zur Entscheidbarkeit und Aufzählbarkeit=