Information Technology Reference
In-Depth Information
CHAPTER
Machines with Memory
As we saw in Chapter
1
, every finite computational task can be realized by a combinational
circuit. While this is an important concept, it is not very practical; we cannot afford to design
a special circuit for each computational task. Instead we generally perform computational tasks
with machines having memory. In a strong sense to be explored in this chapter, the memory of
such machines allows them to reuse their equivalent circuits to realize functions of high circuit
complexity.
In this chapter we examine the deterministic and nondeterministic finite-state machine
(FSM), the random-access machine (RAM), and the Turing machine. The finite-state machine
moves from state to state while reading input and producing output. The RAM has a central
processing unit (CPU) and a random-access memory with the property that each memory
word can be accessed in one unit of time. Its CPU executes instructions, reading and writing
data from and to the memory. The Turing machine has a control unit that is a finite-state
machine and a tape unit with a head that moves from one tape cell to a neighboring one in
each unit of time. The control unit reads from, writes to, and moves the head of the tape unit.
We demonstrate through simulation that the RAM and the Turing machine are universal
in the sense that every finite-state machine can be simulated by the RAM and that it and the
Turing machine can simulate each other. Since they are equally powerful, either can be used as
a reference model of computation.
We also simulate with circuits computations performed by the FSM, RAM, and Turing
machine. These circuit simulations establish two important results. First, they show that all
computations are constrained by the available resources, such as space and time. For example,
if a function
f
is computed in
T
steps by the RAM with storage capacity
S
(in bits), then
S
and
T
must satisfy the inequality
C
Ω
(
f
)=
O
(
ST
)
,where
C
Ω
(
f
)
is the size of the smallest
circuit for
f
over the complete basis
Ω
. Any attempt to compute
f
on the RAM using space
S
and time
T
whose product is too small will fail. Second, an
O
(log
ST
)
-space,
O
(
ST
)
-time
program exists to write the descriptions of circuits simulating the above machines. This fact
leads to the identification in this chapter of the first examples of
P
-complete and
NP
-complete
problems.
91
Search WWH ::
Custom Search