Information Technology Reference
In-Depth Information
inputs of length
n
in time
O
(
n
+
r
(
n
))
and temporary space
r
(
n
)
, writes the string
a
r
(
n
)
(
unary
notation
for
r
(
n
))
on one of its tapes and halts.
Thus, if a resource function
r
(
n
)
is proper, there is a DTM,
M
r
, that given an input of length
n
can write
r
(
n
)
markers on one of its tapes within time
O
(
n
+
r
(
n
))
and space
r
(
n
)
.Another
DTM,
M
,canuseacopyof
M
r
to mark
r
(
n
)
squares on a tape that can be used to stop
M
after exactly
Kr
(
n
)
steps for some constant
K
. The resource function can also be used to
insure that
M
uses no more than
Kr
(
n
)
cells on its work tapes.
8.4 Serial Computational Models
We consider two serial computational models in this chapter, the random-access machine
(RAM) introduced in Section
3.4
and the Turing machine defined in Chapter
5
.
In this section we show that, up to polynomial differences in running time, the random-
access and Turing machines are equivalent. As a consequence, if the running time of a problem
on one machine grows at least as fast as a polynomial in the length of a problem instance, then
it grows equally fast on the other machine. This justifies using the Turing machine as basis for
classifying problems by their serial complexity.
In Sections
8.13
and
8.14
we examine two parallel models of computation, the logic circuit
and the parallel random-access machine (PRAM).
Before beginning our discussion of models, we note that any model can be considered
either serial or parallel. For example, a finite-state machine operating on inputs and states
represented by many bits is a parallel machine. On the other hand, a PRAM that uses one
simple RAM processor is serial.
8.4.1 The Random-Access Machine
The random-access machine (RAM) is introduced in Section
3.4
.(SeeFig.
8.2
.) In this section
we generalize the simulation results developed in Section
3.7
by considering a RAM in which
words are of potentially unbounded length. This RAM is assumed to have instructions for
Random-Access Memory
CPU
cmd
Decode
ALU
out wrd
reg
a
reg
b
in wrd
prog ctr
addr
Figure 8.2
A RAM in which the number and length of words are potentially unbounded.
Search WWH ::
Custom Search