Universal Turing Machines, Part 9: Fin

2007/07/05 · by · in Comp*

The last routine left us with markings on the bits of the current state. Conveniently, it also left us to the left, while the UTM’s Start state has a loop which moves right to check wether or not a symbol is marked on the simulated tape. We’ll simply modify this loop to clean up after ourselves, and viola!

\xymatrix { & &*++[F-:<5pt>]{{Find\ Next} \atop {State}} \ar[dl]{} &*++[F-:<5pt>]{{\scriptstyle Copy\ State\ to} \atop {\scriptstyle Register}} \ar[l]{} &*++[F-:<5pt>]{{Move\ Tape} \atop {Subroutine}} \ar[l]{} \\ *++[][]{} \ar[r] &*++[F-]{Start} \ar[r]^{T \rightarrow T,R} \ar@(ur,ul)_{ \scriptstyle R \atop {{\scriptstyle \overline{0} \rightarrow 0,R} \atop {\scriptstyle \overline{1} \rightarrow 1,R}}} &*++[o][F-]{Hit \atop Tape} \ar[d]^{\Box \rightarrow \overline{s},L} \ar@(ur,ul)_{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[u]{} \\ & &*++[F-:<5pt>]{{\scriptstyle Copy\ Blank} \atop {\scriptstyle Subroutine}} \ar `l[l] [ul]{} \\ }

Weighing in at 17 symbols and 58 states we have some python code and output for a simulation of the (01)* Turing machine.