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

the minimum number of gates necessary to compute f with a circuit. A similar interpretation
can be given to the second inequality involving circuit depth.
The first inequality of Theorem 3.1.1 and the interpretation given to T

C Ω ( δ , λ ) justify
the following definitions of computational work and power. Here power is interpreted as
the time rate at which work is done. These measures correlate nicely with our intuition that
machines that contain more equivalent computing elements are more powerful.

·

DEFINITION 3.1.2 The computational work done by an FSM M =(Σ , Ψ , Q , δ , λ , s , F ) is
TC Ω ( δ , λ ) , the number of equivalent logical operations performed by M , which is the product of
T , the number of steps executed by M ,and C Ω ( δ , λ ) , the size complexity of its next-state and output
functions. The power of an FSM M is C Ω ( δ , λ ) , the number of logical operations performed by
M per step.

Theorem 3.1.1 is also a form of impossibility theorem : it is impossible to compute func-
tions f for which TC Ω ( δ , λ ) and TD Ω ( δ , λ ) are respectively less than the size and depth
complexity of f . It may be possible to compute a function on some points of its domain
with smaller values of these parameters, but not on all points. The halting problem, another
example of an impossibility theorem, is presented in Section 5.8.2 . However, it deals with the
computation of functions over infinite domains.
The inequalities of Theorem 3.1.1 also place upper limits on the size and depth complex-
ities of functions that can be computed in a bounded number of steps by an FSM, regardless
of how the FSM performs the computation.
Note that there is no guarantee that the upper bounds stated in Theorem 3.1.1 are at all
close to the lower bounds. It is always possible to compute a function inefficiently, that is, with
resources that are greater than the minimal resources necessary.

3.1.3 Circuits Are Universal for Bounded FSM Computations
We now ask whether the classes of functions computed by circuits and by FSMs executing
a bounded number of steps are different. We show that they are the same. Many different
functions can be computed from the function f ( T )
M

by specializing inputs and/or deleting

outputs.

THEOREM 3.1.2 Every subfunction of the function f ( n )
M

computable by an FSM on n inputs is

computable by a Boolean circuit and vice versa.
Proof A Boolean function on n inputs, f , may be computed by an FSM with 2 n + 1

−

1
states by branching from the current state to one of two different states on inputs 0 and 1
until all n inputs have been read; it then produces the output that would be produced by f
on these n inputs. A fifteen-state version of this machine that computes the EXCLUSIVE OR
on three inputs as a subfunction is shown in Fig. 3.4 .
The proof in the other direction is also straightforward, as described above and repre-
sented schematically in Fig. 3.3 . Given a binary representation of the input, output, and state
symbols of an FSM, their associated next-state and output functions are binary functions.
They can be realized by circuits, as can f ( n M ( s , w )=( q ( n ) , y ) ,thefunctioncomputedby
the FSM on n inputs, as suggested by Fig. 3.3 . Finally, the subfunction f is obtained by
fixing the appropriate inputs, assigning variable names to the remaining inputs, and deleting
the appropriate outputs.