BuK/IIm20/Begriffssammlung

Wiki-Quelltext dieser Seite.

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