Complexity Classes - Models of Computation: Exploring the Power of Computing - page 332

addition, subtraction, shifting left and right by one place, comparison of words, and Boolean
operations of AND , OR ,and NOT (the operations are performed on corresponding components
of the source vectors), as well as conditional and unconditional jump instructions. The RAM
also has load (and store) instructions that move words to (from) registers from (to) the random-
access memory. Immediate and direct addressing are allowed. An immediate address contains
a value, a direct address is the address of a value, and an indirect address is the address of
the address of a value. (As explained in Section 3.10 and stated in Problem 3.10 ,indirect
addressing does not add to the computing power of the RAM and is considered only in the
problems.)
The time on a RAM is the number of steps it executes. The space is the maximum number
of bits of storage used either in the CPU or the random-access memory during a computation.
We simplify the RAM without changing its nature by eliminating its registers, treating
location 0 of the random-access memory as the accumulator, and using memory locations as
registers. The RAM retains its program counter, which is incremented on each instruction
execution (except for a jump instruction, when its value is set to the address supplied by the
jump instruction). The word length of the RAM model is typically allowed to be unlimited,
although in Section 3.4 we limited it to b bits. A RAM program is a finite sequence of RAM
instructions that is stored in the random-access memory. The RAM implements the stored-
program concept described in Section 3.4 .
In Theorem 3.8.1 we showed that a b -bit standard Turing machine (its tape alphabet con-
tains 2 b characters) executing T steps and using S bits of storage ( S/b words) can be simulated
by the RAM described above in O ( T ) steps with O ( S ) bits of storage. Similarly, we showed
that a b -bit RAM executing T steps and using S bits of memory can be simulated by an O ( b ) -
bit standard Turing machine in O ( ST log 2 S ) steps and O ( S log S ) bits of storage. As seen
in Section 5.2 , T -step computations on a multi-tape TM can be simulated in O ( T 2 ) steps on
a standard Turing machine.
If we could insure that a RAM that executes T steps uses a highest address that is O ( T ) and
generates words of fixed length, then we could use the above-mentioned simulation to establish
that a standard Turing machine can simulate an arbitrary T -step RAM computation in time
O ( T 2 log 2 T ) and space O ( S log S ) measured in bits. Unfortunately, words can have length
proportional to O ( T ) (see Problem 8.4 ) and the highest address can be much larger than T due
to the use of jumps. Nonetheless, a reasonably efficient polynomial-time simulation of a RAM
computation by a DTM can be produced. Such a DTM places one ( address, contents )
pair on its tape for each RAM memory location visited by the RAM. (See Problem 8.5 .)
We leave the proof of the following result to the reader. (See Problem 8.6 .)
THEOREM 8.4.1 Every computation on the RAM using time T can be simulated by a deterministic
Tu r i n g ma c h i n e i n O ( T 3 ) steps.
In light of the above results and since we are generally interested in problems whose time
is polynomial in the length of the input, we use the DTM as our model of serial computation.
8.4.2 Turing Machine Models
The deterministic and nondeterministic Turing machines (DTM and NDTM) are discussed
in Sections 3.7 , 5.1 ,and 5.2 .(SeeFig. 8.3 .) In this chapter we use multi-tape Turing machines
to define classes of problems characterized by their use of time and space. As shown in The-