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

The construction of a shallow Boolean circuit for f ( T M is reduced to a five-step problem: 1)
for each input letter x design a circuit whose input and output are representations of states and
which defines the state-to-state mapping Δ x for input letter x ; 2) construct a circuit for the
associative operator that accepts the representations of two state-to-state mappings Δ y and

Δ z and produces a representation for the state-to-state mapping Δ y Δ z ; 3) use the circuit

for in a parallel prefix circuit to produce the T state-to-state mappings; 4) construct a circuit

that combines the representation of the initial state s with that of the state-to-state mapping
Δ w 1 Δ w 2 ···

Δ w j ( s ) ; and 5) construct a circuit for λ that computes an output from the representation of a
state.
We now describe a generic, though not necessarily efficient, implementation of these steps.
Let Q =

Δ w 2 ··· Δ w j to obtain a representation for the successor state Δ w 1

be the states of M . The state-to-state mapping Δ x for the
FSM M needed for the first step can be represented by a

{ q 0 , q 1 , ... , q |Q|− 1 }

| Q |×| Q |

Boolean matrix N ( x )=

{ n ij ( x ) }

in which the entry in row i and column j , n ij ( x ) , satisfies
n i , j ( x )= 1f M moves from state q i to state q j on input x
0 th rwe

Consider again the FSM shown in Fig. 3.10 . The matrices associated with its four pairs of
inputs x

∈{ ( 0, 0 ) , ( 0, 1 ) , ( 1, 0 ) , ( 1, 1 ) }

are shown below, where N (( 0, 1 )) = N (( 1, 0 )) :

⎡ ⎤ ⎡ ⎤

1000
1000
0100
0100

0100
0100
0010
0010

⎣ ⎦ ⎣ ⎦

N (( 0, 0 )) = N (( 0, 1 )) =

⎡
⎣

⎤
⎦

0010
0010
0001
0001

N (( 1, 1 )) =

From these matrices the generic matrix N (( u , v )) parameterized by the values of th e inp u ts (a
pair ( u , v ) in this example) is produced from the following Boolean functions: t = u

∧ v ,the

carry-terminate function , p = u ⊕ v ,the carry-propagate function ,and g = u ∧ v ,the

carry-generate function .

⎡ ⎤

tpg 0
tpg 0
0

⎣ ⎦

N (( u , v )) =

tpg

0 tpg

-vector that has value 1 in the i th position
and zeros elsewhere. Let σ ( i ) N ( x ) denote Boolean vector-matrix multiplication in which ad-
dition is OR and multiplication is AND .Then,foreach i , σ ( i ) N ( x )=( n i ,1 , n i ,2 , ... , n i , |Q| )
is the unit vector denoting the state that M enters when it is in state q i and receives input x .

Let σ ( i ) = ( 0, 0, ... ,0,1,0, ... 0 ) be the unit | Q |