Es seien
. Dann heißt die Funktion
Auch ein Entscheidungsverfahren repräsentiert in natürlicher Weise eine
berechenbare Funktion. Für die spezielle Gestalt dieser Funktion
vergeben wir den folgenden Namen:
Definition: (charakteristische Funktion [9])
Es seien . Dann heißt die Funktion
mit
die charakteristische Funktion von 
bzgl. 
.
Offenbar gilt:
Die Menge ist entscheidbar relativ zu 
ist berechenbar.
Beispiel:
Die charakteristische Funktion der Menge der Primzahlen M ist
mit
Prof. Dr. Reinhard Völler