Universal Turing Machines, Part 7: Registration

2007/06/27 · by · in Comp*

Now it is time to determine the state that we will transition into. Because of the difficulty of matching a sequence of symbols (the little q) that is sitting in the middle of a list (the big Q‘s) we will first copy this symbol to the register.

  1. Scanning left from the Tape marker, we can erase all the symbol markings, until we hit our current state
  2. Scan to the right until we hit the state that we transition into.
  3. Pick up the first uncopied bit (unless we see a Y or X in which case we can stop here and Accept or Reject.) Also, if we see a S, Q, or T then we’ve done all the copying we need to do, and can rewind the tape unmarking everything along the way. Otherwise, we start copying bits one-by-one in a loop.
    • Scan to the left until we hit the Blank Symbol marker.
    • Scan until we hit a bit that has already been copied (or the q at the tape’s beginning).
    • Place a marked version of the copied bit, and return to get the next bit.

\xymatrix @!=3pc { *++[][]{} \ar[d] & &*++[][F=:<5pt>]{Accept} && \\ *++[o][F-]{R_0} \ar@(ur,dr)^{{\scriptstyle \overline{0} \rightarrow 0,L} \atop {\scriptstyle \overline{1} \rightarrow 1,L}} \ar@(ul,dl)_{L} \ar[d]_{\overline{S} \rightarrow \overline{S},R} & &*++[][F=:<5pt>]{Reject} && \\ *++[o][F-]{R_1} \ar@(ul,dl)_{R} \ar[dr]_{q \rightarrow \overline{q},R} && \\ &*++[o][F-]{R_2} \ar[dl]_{0 \rightarrow \overline{0},L} \ar[dr]_{1 \rightarrow \overline{1},L} \ar[r]^{{{\scriptstyle S \rightarrow S,L} \atop {\scriptstyle Q \rightarrow Q,L}} \atop {\scriptstyle T \rightarrow T,L}} \ar `u[uu] `r^r^{} [uur]^(.25){ X \rightarrow X,R } \ar `u[uuu] `^r^{} [uuur]^(.25){Y \rightarrow Y,R} \ar@(ul,dl)_{R} &*++[o][F-]{R_{10}} \ar@(ul,ur)^{{{{\scriptstyle \overline{0} \rightarrow 0,L} \atop {\scriptstyle \overline{1} \rightarrow 1,L}} \atop {{\scriptstyle \overline{Q} \rightarrow Q,L} \atop {\scriptstyle \overline{S} \rightarrow S,L}}} \atop {\scriptstyle \overline{q} \rightarrow q,L}} \ar@(dl,dr)_{L} \ar[r]^{B \rightarrow B,L} & \\ *++[o][F-]{R_3} \ar@(ul,dl)_{L} \ar[d]_{B \rightarrow B,L} & &*++[o][F-]{R_4} \ar@(ur,dr)^{L} \ar[d]^{B \rightarrow B,L} \\ *++[o][F-]{R_5} \ar@(ul,dl)_{L} \ar[d]_{{{\scriptstyle \overline{1} \rightarrow \overline{1},R} \atop {\scriptstyle \overline{0} \rightarrow \overline{0},R}} \atop {\scriptstyle q \rightarrow q,R}} & &*++[o][F-]{R_6} \ar@(ur,dr)^{L} \ar[d]^{{{\scriptstyle \overline{1} \rightarrow \overline{1},R} \atop {\scriptstyle \overline{0} \rightarrow \overline{0},R}} \atop {\scriptstyle q \rightarrow q,R}} \\ *++[o][F-]{R_7} \ar[dr]_{{\scriptstyle 0 \rightarrow \overline{0},R} \atop {\scriptstyle 1 \rightarrow \overline{0},R}} & &*++[o][F-]{R_8} \ar[dl]^{{\scriptstyle 0 \rightarrow \overline{1},R} \atop {\scriptstyle 1 \rightarrow \overline{1},R}} \\ &*++[o][F-]{R_9} \ar@(dl,dr)_{R} \ar[uuuu]_{\overline{q} \rightarrow \overline{q},R} \\ }