Information Technology Reference
In-Depth Information
a
2
q
a
2
q
s
2
q
s
2
q
a
q
s
q
N
(
1,
q
,2
q
+
1
)
N
(
1, 2
q
,4
q
+
1
)
N
(
2
q
+
1,
q
,4
q
+
1
)
a
−q
s
−q
a
−
2
q
s
−
2
q
a
−
2
q
s
−
2
q
...
...
...
Figure 3.29
A decomposition of an
N
(
1, 2
q
,4
q
+
1
)
circuit.
C
(
1, 2
q
,4
q
+
1
)
≤
C
(
1,
q
,2
q
+
1
)+
C
(
2
q
+
1,
q
,4
q
+
1
)
(3.4)
D
(
1, 2
q
,4
q
+
1
)
≤
D
(
1,
q
,2
q
+
1
)+
D
(
2
q
+
1,
q
,4
q
+
1
)
When the number of tape cells is bounded, the above construction and recurrences
can be modified. Let
m
=
2
p
be the maximum number of cells used during a
T
-step
computation by the TM. We simulate this computation by placing the head over the middle
of a tape with 2
m
+
1 cells. It follows that at least
m
steps are needed to reach each of the
reachable cells. Thus, if
T
≤
m
, we can simulate the computation with an
N
(
1,
T
,2
T
+
1
)
circuit. If
T
≥
m
, we can simulate the first
m
steps with an
N
(
1,
m
,2
m
+
1
)
circuit and
the remaining
T
copies of an
N
(
2
m
+
1,
m
,4
m
+
1
)
circuit.
This follows because at the end of the first
m
steps the head is over the middle 2
m
+
1of
4
m
+
1 cells (of which only 2
m
+
1 are used) and remains in this region after
m
steps due
to the limitation on the number of cells used by the TM.
From the above discussion we have the following bounds on the size
C
(
T
,
m
)
and depth
D
(
T
,
m
)
of a simulating circuit for a
T
-step,
m
-word TM computation:
−
m
steps with
(
T
−
m
)
/m
C
(
1,
T
,2
T
+
1
)
T
≤
m
C
(
1,
m
,2
m
+
1
)+
m
−
1
C
(
2
m
+
1,
m
,4
m
+
1
)
C
(
T
,
m
)
≤
T
≥
m
(3.5)
D
(
1,
T
,2
T
+
1
)
T
≤
m
D
(
1,
m
,2
m
+
1
)+
m
−
1
D
(
2
m
+
1,
m
,4
m
+
1
)
D
(
T
,
m
)
≤
T
≥
m
We complete the proof of Theorem
3.9.8
by bounding
C
(
1, 2
q
,4
q
+
1
)
,
C
(
2
q
+
1,
q
,4
q
+
1
)
,
D
(
1, 2
q
,4
q
+
1
)
,and
D
(
2
q
+
1,
q
,4
q
+
1
)
appearing in (
3.4
)andcom-
bining them with the bounds of (
3.5
).
We now give a recursive construction of an
N
(
2
q
+
1,
q
,4
q
+
1
)
circuit from which
these bounds are derived. Shown in Fig.
3.30
is the recursive decomposition of an
N
(
4
t
+
1, 2
t
,8
t
+
1
)
circuit in terms of two copies of
N
(
2
t
+
1,
t
,4
t
+
1
)
circuits. The
t
-centering cir-
cuits detect whether the head is in positions 2
t
,2
t
2
t
.
In the former case, this circuit cyclically shifts the 8
t
+
1 inputs inputs down by
t
positions;
in the latter, it cyclically shifts them up by
t
positions. The result is that the head is centered
in the middle 2
t
+
1 positions. The
OR
of
s
−
1
,
...
,
s
−
2
t
can be used as a signal to determine
−
1,
...
,1,0orinpositions
−
1,
...
,
−
Search WWH ::
Custom Search