BuK/IIm20/Begriffssammlung

Wiki-Quelltext dieser Seite.

== TODO ==

- Unterschiede Mengen und Funktionen

- 

== 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 ==

[[Bild:Mengen.png]]