1 ステップの算術化

関数 $\mathrm{Step}(e,c)$ を次で定める。$c=\langle q,l,a,r\rangle$ とし、$M_e$ の規則 $(q,a)\mapsto(q',b,d)$ があれば

• $d=R$ のとき $\mathrm{Step}(e,c)=\langle q',\,3l+b,\ r\bmod3,\ \lfloor r/3\rfloor\rangle$、
• $d=L$ のとき $\mathrm{Step}(e,c)=\langle q',\,\lfloor l/3\rfloor,\ l\bmod3,\ 3r+b\rangle$、

規則がなければ $\mathrm{Step}(e,c)=c$ とする。$\mathrm{Step}$ は原始再帰的であり、$M_e$ の状況 $c$ の次の状況を表す。