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

ρ ( M ) w

β

Control

Unit

Figure 5.10 The initial configuration of the tape of a universal TM that is prepared to simulate
the TM M on input

w . The left end-of-tape marker is the blank symbol β .

first letter of w follows the rightmost bracket, ] , and is marked by replacing it with its marked
equivalent,

w 1 . The current state q of M is identified by replacing the left bracket, [ ,in q 's
triple by its marked equivalent, [ . U simulates M by reading the marked input symbol a ,
the one that resides under M 's simulated head, and advancing its own head to the triple to
the right of [ that corresponds to a . (Before it moves its head, it replaces [ with [ .) That is, it
advances its head to the first, second, or third tripleassociatedwiththecurrentstatedepending
on whether a is 0, 1, or β . It then changes < to

< and takes
the required action on the simulated tape. If the action requires writing a symbol, it replaces a
with a new marked symbol. If it requires moving M 's head, the marking on a is removed and
the appropriate adjacent symbol is marked. U returns to

< , moves to the symbol following

< and removes the mark.
The UTM U moves to the next state as follows. It moves its head three places to the
right of < after changing it to < ,atwhichpointitistotherightof # , over the first digit
representing the next state. If the symbol in this position is > ,thenextstateis h , the halting
state, and the UTM halts. If the symbol is 1, U replaces it with 1andthenmovesitshead
left to the leftmost instance of [ (the leftmost tape cell contains β , an end-of tape marker). It
marks [ and returns to 1. It replaces 1 with 1 and moves its head right one place. If U finds the
symbol 1, it marks it, moves left to [ ,restoresitto [ and then moves right to the next instance
of [ and marks it. It then moves right to 1 and repeats this operation. However, if the UTM
finds the symbol > , it has finished updating the current state so it moves right to the marked
tape symbol, at which point it reads the symbol under M 's head and starts another transition
cycle. The details of this construction are left to the reader. (See Problem 5.15 .)

5.6 Encodings of Strings and Turing Machines
Given an alphabet with an ordering of its letters, strings over this alphabet have an order

known as the standard lexicographical order , which we now define. In this order, strings of
length n

A

− 1precedestringsoflength n .Thus,if A = { 0, 1, 2 } , 201 < 0001. Among the

strings of length n ,if a and b are in and a<b , then all strings beginning with a precede

those beginning with b . For example, if 0 < 1 < 2in

A

, then 022 < 200. If two
strings of length n havethesameprefix u , the ordering between them is determined by the

A = { 0, 1, 2 }