entscheidbar

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