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:
- <math>\chi'_A \colon A \to \{1\},\;\;a\mapsto 1</math>.
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:
- <math>
\chi'_A \colon B\to \{0,1\},\;\;a\mapsto \begin{cases}
1 & \mbox{ falls } a \in A \\
\mbox{undefiniert} & \mbox{ sonst }
\end{cases} </math>
Semi-Entscheidbarkeit
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-entscheidbar 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.