uebung3
Aus ProgrammingWiki
Archivierte Version vom 2013-04-09T18:03:16+00:00. Aktuelle Version
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.