Halbe charakteristische Funktion
Die halbe charakteristische Funktion oder partielle charakteristische Funktion ist eine Funktion der Mathematik, die eine Menge identifiziert. Sie ist folgendermaßen definiert: χ'A : A → {1}, a → 1.
Wie man sehen kann, steckt die ganze „Magie“ der Funktion im Definitionsbereich. Ist nun A eine Teilmenge einer größeren Menge B, so ist χ'A auf B\A undefiniert. Man erhält dann:
[Bearbeiten] Semi-Berechenbarkeit
Die halbe charakteristische Funktion kann auf B alle Elemente nennen, die zu A gehören, aber Elemente, die nicht zu A gehören, nicht recht ausschließen. Man spricht davon, χ'A sei partiell. Ist nun χ'A außerdem berechenbar, so nennt man A semi-berechenbar oder rekursiv aufzählbar, da man zwar alle Elemente aufzählen kann, aber die Elemente B\A nicht ausschließen kann. Dafür benötigt man die charakteristische Funktion, die total ist.
