Begriffssammlung

Funktion

surjektiv

injektiv

abzählbar

Eine unendliche Menge M heißt abzählbar unendlich, wenn es eine bijektive Funktion \mathbf{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^* ist (absolut) entscheidbar, wenn M zu A^* relativ entscheidbar ist, d.h. wenn \chi_{M, A^*}, kurz: \chi_M, mit

$\chi_M(w) = \begin{array} wahr, wenn w \in M \\ falsch, wenn w \in A^* \minusset M \end{array}

eine total berechenbare Funktion ist.

semi-entscheidbar

aufzählbar

Eine Menge M \subseteq A^* heißt (rekursiv) aufzählbar, engl. recursively enumerable, wenn es entweder eine total berechenbare surjektive Funktion f: \mathbf{N} \rightarrow M gibt, oder es gilt M = \emptyset. Man nennt f eine Aufzählprozedur oder eine Aufzählverfahren von M.