Information Technology Reference
In-Depth Information
address
addr
in the simulated RAM memory unit, interprets it as an instruction, and then
executes the instruction (which might require a few additional accesses to the memory unit
to read or write data). We return to the simulation of the RAM CPU after we examine the
simulation of the RAM memory unit.
The TM can find a word at location
addr
as follows. It reads the most significant bit
of
addr
and moves right on its tape until it finds the first word with this most significant
bit. It leaves a marker at this location. (The symbol
♦
in Fig.
3.24
identifies the first place
a marker is left.) It then returns to the left-hand end of the tape and obtains the next most
significant bit of
addr
. It moves back to the marker
♦
and then carries this marker forward
to the next address containing the next most significant bit (identified by the marker
♠
in
Fig.
3.24
). This process is repeated until all bits of
addr
have been visited, at which point
the word at location
addr
in the simulated RAM is found. Since
m
tape unit cells are used
in this simulation, at most
O
(
m
log
m
)
TM steps are taken for this purpose.
The TM must also simulate internal RAM CPU computations. Each addition, sub-
traction, and comparison of
b
-bit words can be done by the TM control unit in a constant
number of steps, as can the logical vector operations. (For simplicity, we assume that the
RAM does not use its I/O registers. To simulate these operations, either other tapes would
be used or space would be reserved on the single tape to hold input and output words.) The
jump instructions as well as the incrementing of the program counter require moving and
incrementing
-bit addresses. These cannot be simulated by the TM control unit
in a constant number of steps since it can only operate on
b
-bit words. Instead, they are
simulated on the tape by moving addresses in
b
-bit blocks. If two tape cells are separated
by
q
log
m
1 cells, 2
q
steps are necessary to move each block of
b
bits from the first cell to the
second. Thus, a full address can be moved in 2
q
−
log
m
/b
steps. An address can also
be incremented using ripple addition in
steps using operations on
b
-bit words,
since the blocks of an address are contiguous. (See Section
2.7
for a discussion of ripple
addition.) Thus, both of these address-manipulation operations can be done in at most
O
(
m
log
m
/b
)
steps, since no two words are separated by more than
O
(
m
)
cells.
Now consider the general case of a TM with word size comparable to that of the RAM,
that is, a size too small to hold an address as well as a word. In particular, consider a TMwith
b
-bit tape alphabet where
b
=
cb
,
c>
1 a constant. In this case, we divide addresses into
log
m
/b
/b
b
-bit words and place these words in locations that precede the value of the
RAM word at this address, as suggested in Fig.
3.40
. We also place the address
addr
at the
beginning of the tape in the same number of tape words. A total of
O
((
m/b
)(log
m
))
O
(
b
)
-
bit words are used to store all this data. Now assume that the TM can carry the contents of
a
b
-bit word in its control unit. Then, as shown in Problem
3.26
, the extra symbols in the
TM's tape alphabet can be used as markers to find a word with a given address in at most
O
((
m/b
)(log
2
m
))
TM steps using storage
O
((
m/b
)log
m
)
. Hence each RAM memory
access translates into
O
((
m/b
)(log
2
m
))
TMstepsonthismachine.
Simulation of the CPU on this machine is straightforward. Again, each addition, sub-
traction, comparison, and logical vector operation on
b
-bit words can be done in a constant
number of steps. Incrementing of the program counter can also be done in
log
m
operations since the cells containing this address are contiguous. However, since a jump op-
eration may require moving an address by
O
(
m
)
cells in the
b
∗
-bit TM, it may now require
log
m
/b
moving it by
O
(
m
(log
m
)
/b
)
cells in the
b
-bit TM in
O
m
((log
m
)
/b
)
2
steps.
Search WWH ::
Custom Search