Universal Turing Machines, Part 4: Symbol Lookup
All right, so far we are assured that a marked symbol is on the simulated tape, and the machine head somewhere nearby. We will now have to find the appropriate transition rule in the encoded machine. We will loop through the possible transition functions until we find one that matches with the symbol on the tape.
- Scan to the Left until we find the marked transition state, Q.
- Scan to the Right until we find a transition symbol S, and mark it with a S.
- Grab the most significant bit of this symbol’s number that hasn’t already undergone a comparison, or exit if the comparison has completely finished and no more bits are left.
- Scan to the Right until we find the marked symbol on the tape.
- Skip past the bits that have already been compared.
- If we match, then go back to step 3 and pick up the next bit in the symbol.
- If not, then go back, erasing all of our markings along the way, to step 2 and pick up the next candidate symbol in the transition table.
![\xymatrix @!=3pc {
&*++[][]{}\ar[r]{}
&*++[o][F-]{S_0} \ar@(r,u)_{L}
\ar[d]_{\overline{Q} \rightarrow \overline{Q},R}
&\\
&
&*++[o][F-]{S_1} \ar@(ur,dr)^{R}
\ar[d]_{S \rightarrow \overline{S},R}
&\\
&
&*++[o][F-]{S_2} \ar[r]^{ {\scriptstyle L \rightarrow L,R}
\atop
{\scriptstyle R \rightarrow R,R} }
\ar[dl]_{0 \rightarrow \overline{0},R}
\ar[dr]^{1 \rightarrow \overline{1},R}
&\\
&*++[o][F-]{S_3} \ar@(ul,dl)_{R}
\ar[d]_{\overline{s} \rightarrow \overline{s},R}
&*++[o][F-]{S_8} \ar@(ur,dr)^{L}
\ar[u]^(.3){ {\scriptstyle \overline{0} \rightarrow \overline{0},R}
\atop
{\scriptstyle \overline{1} \rightarrow \overline{1},R} }
&*++[o][F-]{S_4} \ar@(ur,dr)^{R}
\ar[d]^{\overline{s} \rightarrow \overline{s},R}
\\
&*++[o][F-]{S_5} \ar@(ul,dl)_{ {\scriptstyle \overline{0} \rightarrow \overline{0},R}
\atop
{\scriptstyle \overline{1} \rightarrow \overline{1},R} }
\ar[r]^{0 \rightarrow \overline{0},L}
\ar[dr]_{1 \rightarrow 1,L}
&*++[o][F-]{S_7} \ar@(dl,dr)_{ {\scriptstyle \overline{0} \rightarrow \overline{0},L}
\atop
{\scriptstyle \overline{1} \rightarrow \overline{1},L} }
\ar[u]^{\overline{s} \rightarrow \overline{s},L}
&*++[o][F-]{S_6} \ar@(ur,dr)^{ {\scriptstyle \overline{0} \rightarrow \overline{0},R}
\atop
{\scriptstyle \overline{1} \rightarrow \overline{1},R} }
\ar[l]_{1 \rightarrow \overline{1},L}
\ar[dl]^{0 \rightarrow 0,L}
\\
&
&*++[o][F-]{S_9} \ar@(ur,dr)^{L}
\ar@(dr,dl)^{{\scriptstyle \overline{0} \rightarrow 0,L} \atop {\scriptstyle \overline{1} \rightarrow 1,L}}
\ar `l[ll]_{ \overline{S} \rightarrow S,R} `u[uuuu] [uuuu]
\\
}](http://www.cogitolingua.net/blog/wp-content/plugins/wp-latexrender/pictures/758cce6b9a8474e1cd162e7871918b93.png "\xymatrix @!=3pc {
&*++[][]{}\ar[r]{}
&*++[o][F-]{S_0} \ar@(r,u)_{L}
\ar[d]_{\overline{Q} \rightarrow \overline{Q},R}
&\\
&
&*++[o][F-]{S_1} \ar@(ur,dr)^{R}
\ar[d]_{S \rightarrow \overline{S},R}
&\\
&
&*++[o][F-]{S_2} \ar[r]^{ {\scriptstyle L \rightarrow L,R}
\atop
{\scriptstyle R \rightarrow R,R} }
\ar[dl]_{0 \rightarrow \overline{0},R}
\ar[dr]^{1 \rightarrow \overline{1},R}
&\\
&*++[o][F-]{S_3} \ar@(ul,dl)_{R}
\ar[d]_{\overline{s} \rightarrow \overline{s},R}
&*++[o][F-]{S_8} \ar@(ur,dr)^{L}
\ar[u]^(.3){ {\scriptstyle \overline{0} \rightarrow \overline{0},R}
\atop
{\scriptstyle \overline{1} \rightarrow \overline{1},R} }
&*++[o][F-]{S_4} \ar@(ur,dr)^{R}
\ar[d]^{\overline{s} \rightarrow \overline{s},R}
\\
&*++[o][F-]{S_5} \ar@(ul,dl)_{ {\scriptstyle \overline{0} \rightarrow \overline{0},R}
\atop
{\scriptstyle \overline{1} \rightarrow \overline{1},R} }
\ar[r]^{0 \rightarrow \overline{0},L}
\ar[dr]_{1 \rightarrow 1,L}
&*++[o][F-]{S_7} \ar@(dl,dr)_{ {\scriptstyle \overline{0} \rightarrow \overline{0},L}
\atop
{\scriptstyle \overline{1} \rightarrow \overline{1},L} }
\ar[u]^{\overline{s} \rightarrow \overline{s},L}
&*++[o][F-]{S_6} \ar@(ur,dr)^{ {\scriptstyle \overline{0} \rightarrow \overline{0},R}
\atop
{\scriptstyle \overline{1} \rightarrow \overline{1},R} }
\ar[l]_{1 \rightarrow \overline{1},L}
\ar[dl]^{0 \rightarrow 0,L}
\\
&
&*++[o][F-]{S_9} \ar@(ur,dr)^{L}
\ar@(dr,dl)^{{\scriptstyle \overline{0} \rightarrow 0,L} \atop {\scriptstyle \overline{1} \rightarrow 1,L}}
\ar `l[ll]_{ \overline{S} \rightarrow S,R} `u[uuuu] [uuuu]
\\
}")
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}}
\\
&
&*++[F-:<5pt>]{{\scriptstyle Copy\ Blank} \atop {\scriptstyle Subroutine}} \ar `l[l] [ul]{}\\
}](http://www.cogitolingua.net/blog/wp-content/plugins/wp-latexrender/pictures/d99b39114bfc4f98265bf26791c32320.png "\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}}
\\
&
&*++[F-:<5pt>]{{\scriptstyle Copy\ Blank} \atop {\scriptstyle Subroutine}} \ar `l[l] [ul]{}\\
}")