Construction of Universal Turing Machine
We describe Universal Turing Machine U as a 5-tape Turing machine so our universal Turing machine has four tapes:
- The input tape: a read-only tape containing the input, which is never overwritten;
- The description tape: a tape containing the description of M, which is written once at initialization time and never overwritten afterwards;
- The working tape: a tape whose contents correspond to the contents of M’s tape, translated into-bit blocks of binary symbols separated by commas, as the computation proceeds.
- The state tape: a tape describing the current state of M, encoded as an-bit block of binary symbols
- The special tape: a tape containing the binary encodings of the special states {halt, yes, no} and the “directional symbols” {←, →, −}.
The state tape solves the mystery of how a machine with a finite number of states can simulate a machine with many more states: it encodes these states using a tape that has the capacity to hold an unbounded number of symbols. It would be too complicated to write down a diagram of the entire state transition function of a universal Turing machine, but we can describe it in plain English and pseudo code. The machine begins with an initialization phase in which it performs the following tasks:
- Copy the description of M onto the description tape
- Copy the input string x onto the working tape, inserting commas between each-bit block.
- Copy the starting state of M onto the state tape.
- Write the identifiers of the special states and directional symbols onto the special tape.
- Move each cursor to the leftmost position on its respective tape.
After this initialization, the universal Turing machine executes its main loop. Each iteration of the main loop corresponds to one step in the computation executed by M on input x. At the start of any iteration of U’s main loop, the working tape and state tape contain the binary encodings of M’s tape contents and its state at the start of the corresponding step in M’s computation. Also, when U begins an iteration of its main loop, the cursor on each of its tapes except the working tape is at the leftmost position, and the cursor on the working tape is at the location corresponding to the position of M’s cursor at the start of the corresponding step in its computation. (In other words, U’s working tape cursor is pointing to the comma preceding the binary encoding of the symbol that M’s cursor is pointing to). The first step in an iteration of the main loop is to check whether it is time to halt. This is done by reading the contents of M’s state tape and comparing it to the binary encoding of the states “halt”, “yes”, and “no”, which are stored on the special tape. Assuming that M is not in one of the states “halt”, “yes”, “no”, it is time to simulate one step in the execution of M. This is done by working through the segment of the description tape that contains the strings δ1, δ2, . . . , δN describing M’s transition function. The universal Turing machine moves through these strings in order from left to right. As it encounters each pair (q, σ), it checks whether q is identical to the ℓ-bit string on its state tape and σ is identical to the ℓ-bit string on its working tape. These comparisons are performed one bit at a time, and if either of the comparisons fails, then U rewinds its state tape cursor back to the and it rewinds its working tape cursor back to the comma that marked its location at the start of this iteration of the main loop. It then moves its description tape cursor forward to the description of the next rule in M’s transition function. When it finally encounters a pair (q, σ) that matches its current state tape and working tape, then it moves forward to read the corresponding (p, τ, d), and it copies p onto the state tape, τ onto the working tape, and then moves its working tape cursor in the direction specified by d. Finally, to end this iteration of the main loop, it rewinds the cursors on its description tape and state tape back to the leftmost position. It is worth mentioning that the use of five tapes in the universal Turing machine is overkill. In particular, there is no need to save the input ►M; x ⨿ on a separate read-only input tape. As we have seen, the input tape is never used after the end of the initialization stage. Thus, for example, we can skip the initialization step of copying the description of M from the input tape to the description tape; instead, after the initialization finishes, we can treat the input tape henceforward as if it were the description tape.
