Die charakteristische Funktion ist definiert durch: Misplaced &1 & \text{für} \ \omega \in A \\ 0 & \text{für} \ \omega \notin A \end{cases}$$ Eine Menge $A \subseteq \Sigma^*$ heißt [[Entscheidbarkeit|entscheidbar]], falls die charakteristische Funktion berechenbar ist.