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

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:

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.

Siehe auch 
 Rekursiv aufzählbare Menge

Berechenbarkeitstheorie