The Universal TM
The Universal Turing Machine, which we will call $T$, should be
a machine that takes input
$e(M)e(w)$, where $M$ is a TM, $w$ is an input string over the
input alphabet of $M$, and $e(\cdot)$ is the encoding function,
and
simulates machine $M$ running on input $w$.
That means $T$ halts on input $e(M)e(w)$ if and only if $M$
halts on input $w$. Moreover, $T$ halts on input $e(M)e(w)$
with the tape head pointing to $0$ with $1$s on either side (the
encoding of □) if and only if $M$ halts on input $w$ with
the tape head pointing to □.
We will not go over how to construct the Universal TM in
excruciating detail. But it's important to get the big
picture - enough so you recognize that you could, in fact,
build one. First of all, we will build this as a TM with three
tapes, each with its own independent tape head. As we've seen
before, such a machine can be transformed into a simple
one-tape machine.
Initially, the three-tape machine simply has the input on tape 1
and nothing on tapes 2 or 3:
The start state from $e(M)$ is copied onto tape 3, and a $\$$
symbol is written to the cell that separates the start state
portion of tape 1 from the transitions.
From this point on, tape 3 holds a representation of "the state"
for the machine $M$ we are simulating.
The encoded input $e(w)$ portion is copied onto tape 2.
From this point on, tape 2 holds a representation of "the
tape" for the machine $M$ we are simulating.
So in the above example, $M$ would be in state $q_1$ and
the tape would have $a_0a_1a_0$ followed by an infinite number
of blanks. The position of the tape head on tape 2 indicates
the position of the tape head for the machine $M$ we are simulating.
Simulating one step of computation in $M$ consists of:
-
Start at the $\$$ on tape 1 and search for a transition
on the tape whose first block of zeros matches the encoded
state on tape 3, and whose second block of zeros matches
the block of zeros where the tape 2 tape head is currently
at.
-
From the transition found in Step 1,
copy the third block of zeros (state-we-go-to) onto tape
3, overwriting what we had there before.
-
From the transition found in Step 1,
copy the fourth block of zeros (symbol-we-write) onto tape
2. We are "overwriting" the character that was already at
that position, which may mean shrinking or expanding the
space for the block of zeros.
-
From the transition found in Step 1, read the last block
of zeros. If there are two zeros, move the tape 2 head left by one block of
zeros.
If there are three zeros, move the tape 2 head right by one block of
zeros.
If there is only one zero, leave the tape 2 head where it is
The details can be tricky, but this is the gist.
