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

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

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$.