Information Technology Reference
In-Depth Information
THEOREM
3.6.1
Let
f
be a subfunction of
f
(
T
,
m
,
b
)
RAM
, the function computed by the
m
-word,
b
-bit
RAM with storage capacity
S
=
mb
in
T
steps. Then the following bounds hold simultaneously
over the standard basis
Ω
0
for logic circuits:
C
Ω
0
(
f
)=
O
(
ST
)
D
Ω
0
(
f
)=
O
(
T
log
S
)
The discussion in Section
3.1.2
of computational inequalities for FSMs applies to this the-
orem. In addition, this theorem demonstrates the importance of the space-time product,
ST
,
as well as the product
T
log
S
. While intuition may suggest that
ST
is a good measure of the
resources needed to solve a problem on the RAM, this theorem shows that it is a fundamental
quantity because it directly relates to another fundamental complexity measure, namely, the
size of the smallest circuit for a function
f
. Similar statements apply to the second inequality.
It is important to ask how tight the inequalities given above are. Since they are both derived
from the inequalities of Theorem
3.1.1
, this question can be translated into a question about
the tightness of the inequalities of this theorem. The technique given in Section
3.2
can be
used to tighten the second inequality of Theorem
3.1.1
so that the bounds on circuit depth
can be improved to logarithmic in
T
without sacrificing the linearity of the bound on circuit
size. However, the coefficients on these bounds depend on the number of states and can be
very large.
3.7 Turing Machines
The Turing machine model is the classical model introduced by Alan Turing in his famous
1936 paper [
338
]. No other model of computation has been found that can compute func-
tions that a Turing machine cannot compute. The Turing machine is a canonical model of
computation used by theoreticians to understand the limits on serial computation, a topic
that is explored in Chapter
5
. The Turing machine also serves as the primary vehicle for the
classification of problems by their use of space and time. (See Chapter
8
.)
The (deterministic) one-tape, bounded-memory
Tu r i n g ma c h i n e ( TM)
consists of two
interconnected FSMs, a
control unit
and a
tape unit
of potentially unlimited storage capacity.
0
1
2
m
−
1
b
Ta p e Un i t
Control
Unit
Figure 3.22
A bounded-memory one-tape Turing machine.
Search WWH ::
Custom Search