(ou Turing calculables)

Soit M=\left(K,\Sigma,\delta,s \left\{h\right\}\right) une MT et \Sigma_0 \subseteq \Sigma un alphabet et \omega \in\Sigma_{0}^{*} .

Si M s'arrête avec l'entrée \omega ( \left( s,\triangleright \underbrace{\sqcup}\omega\right) ) de sorte que \left( s,\triangleright \underbrace{\sqcup}\omega\right) \vdash_{M}^* \left(h,\triangleright \underbrace{\sqcup}\omega\prime\right) avec \omega\prime\in\Sigma_0^* on dit que \omega\prime est le résultat de sortie de ce calcul, on note \omega\prime=M\left(\omega\right) .

Note: ce mot \omega\prime est unique car M est déterministe.

Soit f une fonction \Sigma_0^* \rightarrow \Sigma_0^* . On dit que M calcule f si et seulement si \forall \omega \in \Sigma_0^* M s'arrête avec \omega en entrée et f\left(\omega\right)=M\left(\omega\right) .

Une fonction est dite récursive (ou récursive au sens de Turing) si et seulement si il existe une MT qui la calcule.