Soientt M=\left(K, \Sigma, \delta, s, H\right) une machine de Turing et \left(q_1,w_1 a_1 u_1\right) et \left(q_2,w_2 a_2 u_2\right) deux configuration de M. On dis qu'on passe de la première à la deuxième en un pas de calcul si et seulement si \exists \beta | \beta\in\left(\Sigma \cup \left\{\leftarrow,\rightarrow\right\}\right) tel que

• \delta\left(q_1,a_1\right) = \left(q_2,b\right)
• la situation est l'une de ces trois:
  1. b\in\Sigma, \&\quad a_2=b, w_2=w_1, u_2=u_1
  2. b \; =\; \rightarrow, \text{ et } w_2=w_1 a_1 et
     • soit u_1\ne e \; \Rightarrow \; u_1=a_2 u_2
     • soit u_1 = e \; \Rightarrow \; a_2=\sqcup,u_2=e
  3. b\;=\;\leftarrow, \text{ et } w_1=w_2 a_2 et
     • soit a_1 u_1 = \sqcup\quad \& \quad u_2=e
     • soit u_2 = a_1 u_1

On note alors \displaystyle \left(q_1, w_1 a_1 u_1\right) \vdash_{M} \left(q_2, w_2 a_2 u_2\right)