Inhaltsverzeichnis

Funktionseigenschaften

Eine Funktion ist berechenbar, wenn es einen Algorithmus gibt, der für jedes x effektiv ein y ermittelt. Dieser Algorithmus muss nicht existieren, es reicht auch, zu zeigen, dass es einen Algorithmus dafür geben muss.
- in leichter Sprache: eine Funktion ist berechenbar, wenn ich dafür ein Programm schreiben kann
Eine Funktion ist total, wenn die für alle Eingabewerte ein Ergebnis liefert, also keine undefinierten Bereiche hat.

Eine Menge ist aufzählbar, wenn es eine totale berechenbare surjektive Funktion gibt, die die natürlichen Zahlen auf die Elemente von M abbildet, oder wenn M die leere Menge ist. Diese Funktion ist die Aufzählfunktion von M.
- in leichter Sprache: eine Menge ist aufzählbar, wenn ich sie strukturiert generieren kann
- → Unterschied zu abzählbar: Die Funktion muss berechenbar und total sein. Bei abzählbar muss die Funktion nur existieren und surjektiv sein.

Eine Menge ist abzählbar, wenn es eine surjektive Abbildung der natürlichen Zahlen auf die Elemente der Menge gibt. Es reicht surjektiv, es muss sogar surjektiv sein, weil sonst die endlichen Mengen nicht abzählbar sind.
Eine Menge ist entscheidbar, wenn es eine charakteristische Funktion chi gibt, die zurückgibt, ob ein beliebiges Wort aus A* in der Menge enthalten ist oder nicht. Chi muss total und berechenbar sein.
Eine Menge ist semi-entscheidbar, wenn es eine partielle berechenbare Funktion chi’ gibt, die wahr zurückgibt, wenn ein beliebiges Wort aus A* in der Menge ist.

bijektiv: alle x aus X werden auf je genau ein y aus Y abgebildet. Alle y werden getroffen.
injektiv: alle x auf X werden auf je maximal ein y aus Y abgebildet. Es kann auch sein, dass Elemente aus Y nicht getroffen werden.
surjektiv: alle y aus Y müssen getroffen werden. Es dürfen mehrere x aus X das gleiche y treffen.