Last Updated on
The Universal Turing Machine Emulates Other Turing Machines
As noted, it is easier to describe any UTM as having three tapes, although it does not require them.
The first tape encodes the set of states for the specific Turing machine to be emulated. The second tape is an input for that specific TM. The third tape is a working memory for the current state of the emulated machine.
The UTM’s program must begin by reading the “program tape” to learn the initial state, and note this on the “status” tape. The UTM’s states follow the following processes.
- Read the current cell in the “data tape”.
- Read the “program tape” to find the instruction for the current status and the current data cell, and note this on the “status tape”. This instruction includes the new state.
- If the new state is “halt”, then set the UTM itself into the “halt” state; otherwise proceed to step 4.
- Apply the instruction from the state to the “data tape”. This might rewrite a cell, and move the “data tape” to the right or left.
- Update the “status tape”.
- Continue at step #1 above.
Eventually the Universal Turing machine’s “data tape” will be identical to the tape produced by the standard Turing machine it is emulating, if the UTM is programmed correctly and given the same initial “data tape” as that regular Turing machine.
As well, both should either halt or continue processing forever. If they halt, they would do so in the same “accept” or “reject” state.
The statement that “the UTM emulates the specific Turning machine” means that the final state, and the data tape at completion, will be identical between the UTM and the specific Turing machine it is emulating. Clearly, the UTM must perform more steps than the machine it emulates. In the list above, steps 2 and 5 are extra. A single-tape UTM takes many extra steps to shuffle between the emulated program and the data, both of which are stored on the one tape. Of course, if a specific machine should fail to halt (for a particular input), then the UTM also would continue processing forever.
Decoding Science. One article at a time.