Machines with Memory - Models of Computation: Exploring the Power of Computing - page 124

Combining these results, we see that each step of the RAM may require as many as
O (( m ((log m ) /b ) 2 ) steps of the b -bit TM. This machine uses storage O (( m/b )log m ) .
Since m = S/b , the conclusion of the theorem follows.
This simulation of a bounded-memory RAM by a Turing machine assumes that the RAM
has a fixed number of memory words. Although this may appear to prevent an unbounded-
memory TM from simulating an unbounded-memory RAM, this is not the case. If the Turing
machine detects that an address contains more than the number of bits currently assumed
as the maximum number, it can increase by 1 the number of bits allocated to each memory
location and then resume computation. To make this adjustment, it will have to space out the
memory words and addresses to make space for the extra bits. (See Problem 3.28 .)
Because a Turing machine with no limit on the length of its tape can be simulated by a
RAM, this last observation demonstrates the existence of universal Turing machines ,Tur-
ing machines with unbounded memory (but with fixed-size control units and bounded-size
tape alphabets) that can simulate arbitrary Turing machines. This matter is also treated in
Section 5.5 .
Since the RAM can execute RAM programs, the same is true of the Turing machines. As
mentioned above, it is not hard to see that every Turing machine can be simulated by a RAM
program. (See Problem 3.29 .) As a consequence, the RAM programs are exactly the programs
that can be computed by a Turing machine.
While the above remarks apply to the one-tape Turing machine, they also apply to all other
Turing machine models, such as double-ended and multi-tape Turing machines, because each
of these can also be simulated by the one-tape Turing machine. (See Section 5.2 .)
3.9 Turing Machine Circuit Simulations
Just as every T -step finite-state machine computation can be simulated by a circuit, so can
every T -step Turing machine computation. We give two circuit simulations, a simple one that
demonstrates the concept and another more complex one that yields a smaller circuit. We use
these two simulations in Sections 3.9.5 and 3.9.6 to establish computational inequalities that
must hold for Turing machines. With a different interpretation they provide examples of P -
complete and NP -complete problems. (See also Sections 8.9 and 8.10 .) These results illustrate
the central role of circuits in theoretical computer science.
3.9.1 A Simple Circuit Simulation of TM Computations
We now design a circuit simulating a computation of a Turing machine M that uses m memory
cells and T steps. Since the only difference between a deterministic and nondeterministic
Turing machine is the addition of a choice input to the control unit, we design a circuit for a
nondeterministic Turing machine.
For deterministic computations, the circuit simulation provides computational inequalities
that must be satisfied by computational resources, such as space and time, if a problem is to be
solved by M . Such an inequality is stated at the end of this section.
With the proper interpretation, the circuit simulation of a deterministic computation is an
instance of a P -complete problem, one of the hardest problems in P to parallelize. Here P is
the class of polynomial-time languages. A first P -complete problem is stated in the following
section. This topic is studied in detail in Section 8.9 .