Computability - Models of Computation: Exploring the Power of Computing - page 220

this point Rule (c) is invoked to strip [ s β from the beginning of the string, and Rule (e) strips
β ] from the end, thereby producing the string w 1 , w 2 , ... , w n that was written initially on
M 's t ape .
Rule (b) is used to add blank space at the right-hand end of the tape. Rules (f )-(h)
mimic the transitions of M in reverse order. Rule (f ) says that if M in state p reading x
moves to state q and moves its head right, then M 's configuration contained the substring
p x before the move and x q after it. Thus, we map x q into p x with the rule x q

→

p x .

Similar reasoning is applied to Rule (g). If the transition δ ( p , x )=( q , y ) , y

}
is executed, M 's configuration contained the substring p x before the step and q y after it
because the head does not move.
Clearly, every computation by a TM M can be described by a sequence of configurations
and the transitions between these configurations can be described by this grammar G. Thus,
the strings accepted by M can be generated by G . Conversely, if we are given a derivation
in G , it produces a series of configurations characterizing computations by the TM M in
reverse order. Thus, the strings generated by G are the strings accepted by M .

∈ Γ ∪{ β

By showing that every phrase-structure language can be accepted by a Turing machine, we
will have demonstrated the equivalence between the phrase-structure and recursively enumer-
able languages.

THEOREM 5.4.2 Every phrase-structure language is recursively enumerable.
Proof Given a phrase-structure grammar G , we construct a nondeterministic two-tape TM
M with the property that L ( G )= L ( M ) . Because every language accepted by a multi-tape
TM is accepted by a one-tape TM and vice versa, we have the desired conclusion.
To decide whether or not to accept an input string placed on its first (input) tape, M
nondeterministically generates a terminal string on its second (work) tape using the rules of
G .Todoso,itputs G 's start symbol on its work tape and then nondeterministically expands
it into a terminal string using the rules of G . After producing a terminal string, M compares
the input string with the string on its work tape. If they agree in every position, M accepts
the input string. If not, M enters an infinite loop. To write the derived strings on its work
tape, M must either replace, delete, or insert characters in the string on its tape, tasks well
suited to Turing machines.
Since it is possible for M to generate every string in L ( G ) on its work tape, it can accept
every string in L ( G ) . On the other hand, every string accepted by M is a string that it can
generate using the rules of G . Thus, every string accepted by M is in L ( G ) . It follows that
L ( M )= L ( G ) .

This last result gives meaning to the phrase “recursively enumerable”: the languages ac-
cepted by Turing machines (the recursively enumerable languages) are languages whose strings
can be enumerated by a Turing machine (a recursive device). Since an NDTM can be simu-
lated by a DTM, all strings accepted by a TM can be generated deterministically in sequence.

5.5 Universal Turing Machines
A universal Turing machine is a Turing machine that can simulate the behavior of an arbitrary
Turing machine, even the universal Turing machine itself. To give an explicit construction for
such a machine, we show how to encode Turing machines as strings.