Machine de Turing
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]