Begriffssammlung
Inhaltsverzeichnis |
TODO
- Unterschiede Mengen und Funktionen
- Sätze mit aufnehmen, Beweise?
Funktion
surjektiv
injektiv
abzählbar
Eine unendliche Menge M heißt abzählbar unendlich, wenn es eine bijektive Funktion \mathbb{N} \rightarrow M gibt. Gibt eine solche Funktion nicht, so ist M überabzählbar unendlich.
berechenbar
Eine Funktion f ist berechenbar, wenn es einen Algorithmus gibt, der für jedes x \in D_f den zugehörigen Funktionswert f(x) effektiv ermittelt.
entscheidbar
Eine Menge M \subseteq A^\ast ist (absolut) entscheidbar, wenn M zu A^\ast relativ entscheidbar ist, d.h. wenn \chi_{M, A^\ast}, kurz: \chi_M, mit
\chi_M(w) = \begin{cases} wahr, & \mbox{wenn } \mbox{$w \in M$} \\ falsch, & \mbox{wenn } \mbox{$w \in A^\ast \setminus M$} \end{cases}eine total berechenbare Funktion ist.
semi-entscheidbar
Eine Menge M \subseteq A^\ast ist (absolut) semi-entscheidbar, wenn die partielle (semi-charakteristische) Funktion \chi'_M : A^\ast \rightarrow \{wahr\} mit:
\chi'_M(w) = \begin{cases} wahr, & \mbox{wenn } \mbox{$w \in M$;} \\ \perp, & \mbox{sonst.}\end{cases}berechenbar ist.
aufzählbar
Eine Menge M \subseteq A^\ast heißt (rekursiv) aufzählbar, engl. recursively enumerable, wenn es entweder eine total berechenbare surjektive Funktion f: \mathbb{N} \rightarrow M gibt, oder es gilt M = \emptyset. Man nennt f eine Aufzählprozedur oder eine Aufzählverfahren von M.
Mengenverhältnisse
