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

eine total berechenbare Funktion ist.

semi-entscheidbar

aufzählbar