Erkannte Sprache einer TM

Einfache Sprache

Def. Erkannte Sprache einer TM

Sei $\mathcal M$ eine TM. Die von $\mathcal M$ Erkannte Sprache, geschrieben $L(\mathcal M)$, ist als

$$L(\mathcal M) = \{w\in A^*\mid \mathcal M \textit{ akzeptiert } w\}$$

definiert.

Eine Sprache $L$ heißt rekursiv aufzählbar, wenn eine TM $\mathcal M$ existiert so, dass $L$ die erkannte Sprache von $\mathcal M$ ist. Also

$$L= L(\mathcal M)\;.$$