semi-entscheidbar

Eine Sprache $A\subseteq {\mathrm{\Sigma }}^{\ast }$ heißt semi-entscheidbar, falls die halbe charakteristische Funktion ${\chi }_A^{\ast }:{\mathrm{\Sigma }}^{\ast }\to 0,1$ berechenbar ist. $$\chi_A^{*}(x) = \begin{cases} 1, & \text{falls } x \in A,\[4pt] \text{undefiniert}, & \text{falls } x \notin A. \end{cases}$$