BuK/IIm20/Defitionen Lemke

Wiki-Quelltext dieser Seite.

__TOC__

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

= Mengeneigenschaften =

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

= Abbildungseigenschaften =

* '''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.