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