Une machine de Turing (MT) est un quintuplet M=\left(K,\Sigma,\delta,s,H\right) où

• K est un ensemble fini d'états
• \Sigma est un alphabet (fini) contenant les symboles \sqcup (blanc) et \triangleright (début de mot)
• s\in K : état initial
• H\in K : ensemble des état d'arrêt
• \delta : fonction de transition
  • \delta: \left(K \setminus H\right) \times \Sigma \mapsto K\times \left(\Sigma \cup \left\{ \leftarrow, \rightarrow\right\}\setminus \left\{ \triangleright \right\}\right)
  • \left[\delta\left(p,\triangleright\right)=\left(q,\sigma\right)\right]\Rightarrow\left[\sigma=\rightarrow\right]