Soit
On dit que M semi-décide L (ou accepte L) si et seulement si \forall \omega\in\Sigma_0^*, \quad \omega\in L \Leftrightarrow M s'arrête avec l'entrée \omega.
N.B. : \forall \omega\in\Sigma_0^*, \quad \omega\notin L \Leftrightarrow M boucle à l'infini avec l'entrée \omega.