5.1 Universal Turing Machines 229
concept of the universal Turing machine was conceived by Alan Turing well
before the real digital computers were invented.
In the following, we present a brief description of how the universal DTM
works. We will present it as a three-tape DTM over the tape alphabet (0, 1, B}.
Theorem 4.13 showed that there is an equivalent one-tape DTM for it. There-
fore, there is actually a universal DTM in M.
First, we note that machine U uses only a fixed alphabet (0, 1, B}, whereasmachines MY in M may have a bigger alphabet {al,... , a,}. So, we need
a fixed coding system to encode a string x: in {al,... , urn} by a string x’
in {O,l}. We do this by a simple scheme: the symbol ai is represented by
string Oi, and a string x = u+x~,... czin is represented by the string x’ =
Oil l(y”l... loin.
The machine U uses tape 1 as the input tape. When it starts, the config-
uration of tape 1 is of the form
x;BxI,B l l l Bx;B yB,where y is to be interpreted as the code of machine A&y and x1,... , xk are the
inputs to machine A&. (Note: Here, B denotes the blank symbol of U. The
blank symbol us of A,& is represented by a string O”.) The machine U uses
tape 2 to simulate the tape of machine A&, and uses tape 3 to store the current
state of machine A&. So, tapes 2 and 3 together represent a configuration of
machine A&.
With this setting, the simulation of My can be described as follows:
(1) Initiulixation: First, U copies y to tape 3 and checks whether y is a legal
code of a DTM in M. By Example 5.1, this problem is primitive recursive
and so can be done by a DTM. (Note: Tape 1 is read-only, and so we need to
copy it to tape 3 to do the checking.)
If it is not legal, then machine U copies the inputs (xi,... , XL) to tape 2
and halts (i.e., it accepts the input and outputs the same values as the inputs).
If it is legal, the machine U copies the inputs to tape 2 and writes 0 on tape
3 (to indicate that My is in state q1). The configuration after this initialization
step is
(s, x’,B l l l Bx;Byl3, Ix/11031 l l l 1031x;1031, - - BO).
Again, in the above, B denotes the blank symbol of U and O3 denotes the code
of the blank symbol us of My. Note that the head of tape 2 is scanning the
symbol 1 that lies to the left of the O-block which represents the symbol in
{m,**. , a,} currently scanned by machine My (called the current O-block).
(2) Simulution: Each move of machine My can be simulated as follows:
First, U scans the string y to find an instruction code starting with 1O’lOj 1
where Oi is the current content of tape 3 and Oj is the O-block to the right of
the head of tape 2.
If such an instruction 1Oi 1Oj 10 lOllOh 1 is found, then U simulates the in-
struction accordingly. Namely, it changes the content of tape 3 to Ok, changes
the O-block to the right of the head of tape 2 to Oe, and moves the head of