Machines with Memory - Models of Computation: Exploring the Power of Computing - page 136

a 4 t
s 4 t

a 2 t

a 2 t
s 2 t

s 2 t

a 0
s 0

a − 2 t

a − 2 t

s − 2 t s − 2 t

... ...

a − 4 t
s − 4 t

Figure 3.30 A recursive decomposition of N ( 4 t + 1, 2 t ,8 t + 1 ) .

which shift to take. After centering, t steps are simulated, the head is centered again, and
another t steps are again simulated. Two t -correction circuits cyclically shift the results in
directions that are the reverse of the first two shifts. This circuit correctly simulates the tape
computation over 2 t steps and produces an N ( 4 t + 1, 2 t ,8 t + 1 ) circuit.
A t -centering circuit can be realized as a single stage of the cyclic shift circuit described
in Section 2.5.2 and shown in Fig. 2.8 .A t -correction circuit is just a t -centering circuit
in which the shift is in the reverse direction. The four shifting circuits can be realized with
O ( tb ) gates and constant depth. The two OR trees to determine the direction of the shift can
be realized with O ( t ) gates and depth O (log t ) . From this discussion we have the following
bounds on the size and depth of N ( 4 t + 1, 2 t ,8 t + 1 ) :

C ( 4 t + 1, 2 t ,8 t + 1 ) ≤

2 C ( 2 t + 1, t ,4 t + 1 )+ O ( bt )

C ( 3, 1, 5 ) ≤ O ( b )

D ( 4 t + 1, 2 t ,8 t + 1 ) ≤

2 D ( 2 t + 1, t ,4 t + 1 )+ 2

log 2 t

D ( 3, 1, 5 ) ≤ O ( 1 )

( k )=
D ( 2 t + 1, t ,4 t + 1 ) when t = 2 k . The above bounds translate into the following recurrences:

We now solve this set of recurrences. Let C ( k )= C ( 2 t + 1, t ,4 t + 1 ) and D

( k )+ K 1 2 k + K 2 C ( k + 1 ) ≤ C

2

C ( 0 ) ≤ K 3

D ( k + 1 ) ≤ 2 D ( k )+ 2 k + K 4

D ( 0 ) ≤ K 5

for constants K 1 , K 2 , K 3 , K 4 ,and K 5 . It is straightforward to show that

C ( k + 1 ) and

D ( k + 1 ) satisfy the following inequalities:

2 k ( K 1 k/ 2 + K 2 + K 3 ) C ( k ) ≤ − K 2

2 k ( K 5 + K 4 + 2 ) D ( k ) ≤ − 2 k − ( K 4 + 2 )