$\chi_A$ = Charakteristische Funktion der Menge $A \subseteq \Sigma^*$.
Wenn (semi-)entscheidbar ⇒ $\chi_A$ berechenbar
entscheidbar \[ \chi_A = \begin{cases} 1 & \text{ wenn } w \in A \\ 0 & \text{ wenn } w \not\in A \end{cases} \]
semi-entscheidbar \[ \chi_A = \begin{cases} 1 & \text{ wenn } w \in A \\ \text{undefiniert} & \text{ wenn } w \not\in A \end{cases} \]
Der Algorithmus von $\chi_A$
| Fall | Bedingung | Name |
|---|---|---|
| Ja | Terminiert | entscheidbar |
| Nein | Terminiert | |
| Ja | Terminiert | semi-entscheidbar |
| Nein | Terminiert nicht immer | |
| Ja | Terminiert nicht immer | nicht semi-entscheidbar |
| Nein | Terminiert nicht immer |
Die Menge lässt sich mit natürlichen Zahlen aneinander reihen
$f$ ist total
$M = \{f(1), f(2), f(3), \ldots\}$ bzw. $M = \{x_i | P(x_i)\}$ (Nicht zwangsweise das gegenteil!)
P semi-entscheidbar ⇒ $M_P$ (rekursiv) aufzählbar
„Ich kann die Elemente selbst aufzählen (errechnen)“
„Ich kann die Elemente zwar nicht selbst aufzählen, wenn ich sie bekommen, kann ich sie aber abzählen“