226 COMPUTABUJTY THEORYhard to see that for every Turing-computable function f : (C)k + C, there
exists a DTM AI in M such that AI computes f” : ((0, I))” + {O,l}*, where
f(&, 22,... , &) = 5 if and only if f(~l, ~2,... ,Xk) = y. Therefore, we may
consider a computational system in which the only machines available are
those in M, and the class of Turing-computable functions (under the above
coding system) remains the same.
Coding of Turing Machines. We can encode each DTM M in M itself
by a string in (0, l}* in the following way: First, each instruction Qi, aj) =
(qk, at, Dh ) is encoded by the stringwhere h = 1,2, with D1 representing L and 02 representing R. Then, a
machine in M with t instructions can be encoded by the stringl”code~code2 l l l code& (5 1).
where codei is the code of the ith instruction and b is any integer greater than
- We note that we do not need to encode any other information of M, since
we can find the information from the above code:
(1) & = {!Il,***> an}, where n is the length of the longest third O-block in
an instruction code. (We require that each DTM M in M must contain
a “halting instruction,” even if the machine may never execute it. Also
note that the final state qn does not occur in the first O-block of an
instruction code.)
(2) C=(q,..., a,}, where m is the length of the longest second or fourth
O-block in an instruction code.
(3) The starting state is 41.
(4) The final state is qn.
(5) The blank is 03.
Note that the above coding system is not one-to-one. More precisely, some
strings in (0, 1}* d o not encode any DTM, and many strings encode the same
DTM. To simplify the coding system, we arbitrarily define that a string x E
(0, 1}* represents a fixed empty DT2M ME, if ;t: does not have the above correct
form of a DTM code (e.g., if it begins with 110). This machine ME is defined
as ({Ql, az), {%aah { al, ~22, B}, &, 42)) where & contains a single instruction
&(41,a1) = (42, al, R). Note that ME contains a halting instruction which
will never be executed, since its initial configurations (ql, Bd) do not have a
successor configuration. Thus, it halts and rejects any input x E (0, l}* in
zero move; that is, L(M,) = 0. With this assumption, we see that every string
in (0, 1)’ encodes a DTM in M. Also, each DTM has an infinite number of
codes. We say a string II: E (0, l}* is a legal code if it encodes a nonempty
DTM in the form (5.1).