Universal Turing Machines, Part 5: She Puts the Symbol on the Tape

2007/06/24 · by · in Comp*

The last routine left us conveniently positioned on the s character of the symbol which is to be copied to the marked position on the simulated tape. The marked tape symbol is also fully marked up, so as we copy we will be unmarking its bits, while the symbol in the transition function is not marked at all, but will become so during the copying process.

  1. Mark this symbol so we can come back to it later.
  2. Grab the most significant bit to be copied.
  3. Scan to the Right until we hit the marked symbol on the tape.
  4. Step over the bits already copied.
  5. Place the new bit into its position.
  6. Decide wether we are done or not.
    • If we are on a 0 or 1 then more bits need to be copied. Scan to the Left over the symbol on the tape and back to step 2.
    • If we are on an s or $\Box$ then we’ve copied all the bits and can scan to the Left restoring them to an unmarked state. Finally exiting with the machine head to the Left of the marked tape symbol.

\xymatrix @!=3pc { *++[][]{} \ar[r] &*++[o][F-]{C_0} \ar[d]^{s \rightarrow \overline{s},R} \\ &*++[o][F-]{C_1} \ar[dl]_{0 \rightarrow \overline{0},R} \ar[dr]^{1 \rightarrow \overline{1},R} \\ *++[o][F-]{C_2} \ar@(ul,dl)_{R} \ar[d]_{ \overline{s} \rightarrow \overline{s},R} &*++[o][F-]{C_7} \ar@(dr,ur)_{L} \ar[u]^(.3){{\scriptstyle\overline{0} \rightarrow \overline{0},R} \atop {\scriptstyle\overline{1} \rightarrow \overline{1},R}} &*++[o][F-]{C_3} \ar@(ur,dr)^{R} \ar[d]^{\overline{s} \rightarrow \overline{s},R} \\ *++[o][F-]{C_4} \ar@(ul,dl)_{{\scriptstyle 0 \rightarrow 0,R} \atop {\scriptstyle 1 \rightarrow 1,R}} \ar[r]^{{\scriptstyle \overline{0} \rightarrow 0,R} \atop {\scriptstyle \overline{1} \rightarrow 0,R}} &*++[o][F-]{C_6} \ar[d]_{{\scriptstyle s \rightarrow s,L} \atop {\scriptstyle \Box \rightarrow \Box,L}} \ar[u]^{\overline{s} \rightarrow \overline{s},L} \ar@(u,r)^{L} &*++[o][F]{C_5} \ar@(ur,dr)^{{\scriptstyle 0 \rightarrow 0,R} \atop {\scriptstyle 1 \rightarrow 1,R}} \ar[l]^{{\scriptstyle \overline{0} \rightarrow 1,R} \atop {\scriptstyle \overline{1} \rightarrow 1,R}} \\ &*++[o][F-]{C_8} \ar@(dl,dr)_{L} \ar[r]^{\overline{s} \rightarrow \overline{s},L} & \\ }
Thus our UTM so far looks like
\xymatrix { *++[][]{} \ar[r] &*++[F-]{Start} \ar[r]^{T \rightarrow T,R} \ar@(ur,ul)_{R} &*++[o][F-]{Hit \atop Tape} \ar[d]^{\Box \rightarrow \overline{s},L} \ar@(ur,ul)_{ {\scriptstyle s \rightarrow s,R} \atop {{\scriptstyle 0 \rightarrow 0,R} \atop {\scriptstyle 1 \rightarrow 1,R}} } \ar[r]^(.4){\overline{s} \rightarrow \overline{s},L} &*++[F-:<5pt>]{{Lookup\ New} \atop {Symbol}} \ar[r]{} &*++[F-:<5pt>]{{Write\ Symbol} \atop {on\ Tape}} \ar[r]{} &*++[F-:<5pt>]{{Move\ Tape} \atop {Subroutine}} \\ & &*++[F-:<5pt>]{{\scriptstyle Copy\ Blank} \atop {\scriptstyle Subroutine}} \ar `l[l] [ul]{}\\ }