Universal Turing Machines, Part 8: Lost in Transition

First: Last weekend I met with a friend and we reviewed this UTM subroutine by subroutine, finding a few errata, which have been fixed.

Finally, we’ve reached the end. The last step of simulation is to find and mark the state with has been copied into the register.
This procedure resembles the find symbol subroutine.

1. Move Right until we find an unmarked Q and mark it with a Q.
2. Move Left and step over the B symbol.
3. Keep moving Left and mark all the 0‘s and 1‘s.
4. If we hit the B that means all bits have been verified and we can exit the loop; Else, we pick up and unmark the least significant 0 or 1.
5. Move Right until we hit the state we are trying to verify. (it’ll be designated by a Q)
• If the least significant unmarked bit corresponds to the bit we just picked up, then mark it off and return to pick up the next bit.
• If it doesn’t match, then move back erasing marked bits, until we hit the state marker, Q, and unmark it, stepping to the Right so that we’ll pick up the next state in the next iteration of the loop.