Information Technology Reference
In-Depth Information
machine can be simulated by the RAM, the Turing machine simulating a RAM is universal for
the set of all Turing machines.
Also, because there is a Turing machine that can simulate any RAM computation, every
RAM program can be simulated on this Turing machine. Since it is not hard to see that every
Turing machine can be described by a RAM program (see Problem
3.29
), it follows that the
RAM programs are exactly the programs computed by Turing machines. Consequently, the
RAM is also universal.
The following theorem demonstrates that RAM computations can be simulated by Turing-
machine computations and vice versa when each operates with bounded memory. Note that
all halting computations are bounded-memory computations. A direct proof of the existence
of a universal Turing machine is given in Section
5.5
.
THEOREM
3.8.1
Let
S
=
mb
and
m ≥ b
. Then for every
m
-word,
b
-bit Turing machine
M
TM
(with storage capacity
S
)thereisan
O
(
m
)
-word,
b
-bit RAM that simulates a time
T
computation
of
M
TM
in time
O
(
T
)
and storage
O
(
S
)
. Similarly, for every
m
-word,
b
-bit RAM
M
RAM
there is an
O
((
m/b
)log
m
)
-word,
O
(
b
)
-bit Turing machine that simulates a
T
-time,
S
-storage
computation of
M
RAM
in time
O
(
ST
log
2
S
)
and storage
O
(
S
log
S
)
.
Proof
We begin by describing a RAM that simulates a TM. Consider a
b
-bit RAM program
to simulate an
m
-word,
b
-bit TM. As shown in Theorem
3.4.1
,aRAMprogramcanbe
written to simulate one step of an FSM. Since a TM control unit is an FSM, it suffices to
exhibit a RAM program to simulate a tape unit (also an FSM); this is straightforward, as
is combining the two programs. If the RAM has storage capacity proportional to that of
the TM, then the RAM need only record with one additional word the position of the tape
head. This word, which can be held in a RAM register, is incremented or decremented as
the head moves. The resulting program runs in time proportional to the running time of
the TM.
We now de s c r i be a
b
∗
-bit TM that simulates a RAM, where
b
∗
=
+
b
+
c
for
some constant
c
, an assumption we examine later. Let RAM words and their corresponding
addresses be placed in individual cells on the tape of the TM, as suggested in Fig.
3.24
.Let
the address
addr
of the RAM CPU program counter be placed on the tape of the TM to the
left, as suggested by the shading in the figure. (It is usually assumed that, unlike the RAM,
theTMholdswordsofsizenolargerthan
O
(
b
)
in its control unit.) The TM simulates
a RAM by simulating the RAM fetch-and-execute cycle. This means it fetches a word at
log
m
Figure 3.24
Organization of a tape unit to simulate a RAM. Each RAM memory word
w
j
is
accompanied by its address
j
in binary.
Search WWH ::
Custom Search