Universal Turing Machines, Part 6: Headbashing

2007/06/26 · by · in Comp*

Ok, so we just finished simulating a write, now it’s time to simulate movement of the head to the Left or Right one square.
This routine should be fairly straightforward.

  1. Scan back to the symbol in the transition table and read the L or R.
  2. Scan forward to the marked symbol on the tape.
    • If we are moving to the Right, then sail past and mark the next s, unless we hit a blank, in which case we’re done (because that will be picked up by the Copy Blank Subroutine the next time through the simulation).
    • If we are moving to the Left, then back up and mark the previous s, unless we run of the left end of the Tape, in which case the head is forced to stay on the leftmost square.

\xymatrix @!=3pc { &*++[][]{} \ar[d]^{} \\ &*++[o][F-]{M_0} \ar[d]^{\overline{s} \rightarrow s,L} \ar@(ul,dl)_{ {\scriptstyle\overline{0} \rightarrow 0,L} \atop {\scriptstyle\overline{1} \rightarrow 1,L} } \ar@(ur,dr)^{L} \\ &*++[o][F-]{M_1} \ar[dl]_{L \rightarrow L,R} \ar[dr]^{R \rightarrow R,R} \\ *++[o][F-]{M_2} \ar@(ul,dl)_{R} \ar[d]_{\overline{s} \rightarrow s,L} & &*++[o][F-]{M_3} \ar@(ur,dr)^{R} \ar[d]^{\overline{s} \rightarrow s,R} \\ *++[o][F-]{M_4} \ar@(ul,dl)_{L} \ar `dr^r[dr]^{s \rightarrow \overline{s},L} [drr] \ar[d]_{T \rightarrow T,R} & &*++[o][F-]{M_5} \ar@(ur,dr)^{R} \ar `dl^r[dl]^{ {\scriptstyle s \rightarrow \overline{s},L} \atop {\scriptstyle \Box \rightarrow \Box,L} } [d] &\\ *++[o][F-]{M_6} \ar `r^r[r]_{s \rightarrow \overline{s},L} [rr] &&\\ }