Soit

• M=\left(K, \Sigma, \delta, s,\left\{ h\right\} \right) un MT,
• \Sigma_0 \subseteq \Sigma\setminus \left\{\sqcup ,\triangleright\right\}
• et L \subset \Sigma_0^*

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.