The one-step configuration relation

Fix a deterministic one-tape Turing machine $M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\bigsqcup ,q_0,q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}},\delta )$. Let $C=(q,h,t)$ and $C^{\mathrm{\prime }}=(q^{\mathrm{\prime }},h^{\mathrm{\prime }},t^{\mathrm{\prime }})$ be configurations of $M$.

We say that $C^{\mathrm{\prime }}$ follows $C$ in one step, and write $C{⊢}_M{C}^{\mathrm{\prime }},$ when $q\mathrm{\notin }\{q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}}\}$ and, writing $\delta (q,t(h))=(p,b,D),$ one has:

• $q^{\mathrm{\prime }}=p$,
• $t^{\mathrm{\prime }}(h)=b$,
• $t^{\mathrm{\prime }}(i)=t(i)$ for every $i\mathrm{\ne }h$,
• if $D=R$, then $h^{\mathrm{\prime }}=h+1$,
• if $D=L$ and $h>0$, then $h^{\mathrm{\prime }}=h-1$,
• if $D=L$ and $h=0$, then $h^{\mathrm{\prime }}=0$.

So one step changes only the scanned tape cell, updates the state, and moves the head one cell right or one cell left, except that the left boundary clamps the head at cell $0$.

• Because $t^{\mathrm{\prime }}$ differs from $t$ at at most one position, it is again a finite-support tape content.

• There is no one-step successor from an accepting or rejecting configuration.