Information Technology Reference
In-Depth Information
3.9.7 An Efficient Circuit Simulation of TM Computations*
In this section we construct a much more efficient circuit of size
O
(
Tb
log
m
)
that simulates
a computation done in
T
steps by an
m
-word,
b
-bit one-tape TM. A similar result on circuit
depth is shown.
THEOREM
3.9.8
Let an
m
-word,
b
-bit Turing machine compute in
T
steps the function
f
,a
projection of
f
(
T
,
m
,
b
)
TM
, the function computed by the TM in
T
steps. Then the following bounds on
thesizeanddepthof
f
over the complete basis
Ω
must be satisfied:
C
Ω
(
f
)=
O
(
T
(log[min(
bT
,
S
)])
D
Ω
(
f
)=
O
(
T
)
Proof
The circuit
C
M
,
T
described in Theorem
3.9.1
has size proportional to
O
(
ST
)
,where
S
=
mb
. We now show that a circuit computing the same function,
N
(
1,
T
,
m
)
,canbe
constructed whose size is
O
(
T
(log[min(
bT
,
S
)])
. This new circuit is obtained by more
efficiently simulating the tape unit portion of a Turing machine. We observe that if the head
never reaches a cell, the cell circuit of Fig.
3.26
can be replaced by wires that pass its inputs
to its output. It follows that the number of gates can be reduced if we keep the head near
the center of a simulated tape by “centering” it periodically. This is the basis for the circuit
constructed here.
It simplifies the design of
N
(
1,
T
,
m
)
to assume that the tape unit has cells indexed
from
m
to
m
. Since the head is initially placed over the cell indexed with 0, it is over
the middle cell of the tape unit. (The control unit is designed so that the head never enters
cells whose index is negative.) We construct
N
(
1,
T
,
m
)
from a subcircuit
N
(
c
,
s
,
n
)
that
simulates
s
steps of a tape unit containing
nb
-bit cells under the assumption that the tape
head is initially over one of the middle
c
cells where
c
and
n
are odd. Here
n
−
c
+
2
s
,so
that in
s
steps the head cannot move from one of the middle
c
cells to positions that are not
simulated by this circuit. Let
C
(
c
,
s
,
n
)
and
D
(
c
,
s
,
n
)
be the size and depth of
N
(
c
,
s
,
n
)
.
As base cases for our recursive construction of
N
(
c
,
s
,
n
)
, consider the circuits
N
(
1, 1, 3
)
and
N
(
3, 1, 5
)
. They can be constructed from copies of the tape circuit
≥
C
t
(
5
)
since they simulate one step of tape units containing three and five cells, respectively. In fact,
these circuits can be simplified by removing unused gates. Without simplification
C
t
(
3
)
and
C
t
(
n
)
contains 5
(
b
+
1
)
gates in each of the
n
cell circuits (see Fig.
3.26
)aswellas
(
n
−
1
)
b
gates
in the vector
OR
circuit, for a total of at most 6
n
(
b
+
1
)
gates. It has depth 4
+
log
2
n
.
Thus,
N
(
1, 1, 3
)
and
N
(
3, 1, 5
)
each can be realized with
O
(
b
)
gates and depth
O
(
1
)
.
We now give a recursive construction of a circuit that simulates a tape unit. The
N
(
1, 2
q
,4
q
+
1
)
circuit simulates 2
q
steps of the tape unit when the head is over the middle
cell. It can be decomposed into an
N
(
1,
q
,2
q
+
1
)
circuit simulating the first
q
steps and
an
N
(
2
q
+
1,
q
,4
q
+
1
)
circuit simulating the second
q
steps, as shown in Fig.
3.29
.In
the
N
(
1,
q
,2
q
+
1
)
circuit, the head may move from the middle position to any one of
2
q
+
1 positions in
q
steps, which requires that 2
q
+
1 of the inputs be supplied to it. In the
N
(
2
q
+
1,
q
,4
q
+
1
)
circuit, the head starts in the middle 2
q
+
1 positions and may move
to any one of 4
q
+
1 middle positions in the next
q
steps, which requires that 4
q
+
1inputs
be supplied to it. The size and depth of our
N
(
1, 2
q
,4
q
+
1
)
circuit satisfy the following
recurrences:
Search WWH ::
Custom Search