SOME UNIVERSAL ELEMENTS FOR FINITE AUTOMATA
M. L. Minsky
In recent years a number of theories have appeared all of which
are concerned with the construction of complicated "machinery" from a small
number of basic elements. The neurological models of Rashevsky, and of
Pitts and McCulloch, the more general models of Kleene, and in logic the
combinatorial constructions of Curry and several others, all display
similar features in this regard. In the present paper, it is shown that a
certain category of sets of elements are "universal" in the sense that one
can assemble such elements into machines with which one can realize functions
which are arbitrary to within certain reasonable restrictions. The discus
sion takes place within the framework of Kleene*s theory of "finite automata"
as generalized from the McCulloch-Pitts neurological model [1943).
1 . Elements and Response Functions
An "element" J will be defined as an object with a finite number
of "input fibres" S^ and a finite number of "output fibres61 R^- At any of a
discrete set of "moments" each fibre may be in either of two states, "qui
escent" or "firing." Each element will be assumed to act as though it were
a "finite automaton" in the sense of Kleene (ref.) with the input fibres
playing the role of "input cells" and the output fibres playing the role of
some of the "Inner cells" of the corresponding automaton. It will be further
assumed that each element acts as though it were an "automaton without
cycles," i.e., as though It has a finite set of internal states and that if
no input fibre is fired for a sufficient Interval (of duration d(J) moments)
the element reverts to a basic "quiesccnt" state and so remains at least
until Input activity is resumed.
A few examples of useful elements are listed below:
1 1 7
118
MINSKY
"Con-junctions." This is the McCulloch-Pitts element with
two input fibres and "threshold 2" i.e., the element fires
at time t if and only if both input fibres are fired at
time t - 1 . The element is represented both by the dia
gram and the equation below;
A N
N(t) s A(t - 1 ).B(t - 1 )
"Pis-junctions." This element has also two input fibres
and fires at time t if and only if either or both input
fibres fire at time t - 1 .
A IN.
—
B - N(t) = A(t - 1 ) v B(t - 1 )
iii. "Binary inhibitory junction" or "b. i . j ." This element
has two input fibres E and I and one output fibre. The
input fibres are different in that the element fires at
time t if and only if fibre E is fired at t - 1 and
fibre I is NOT fired at t - 1 .
E „N
I
N(t) = E(t - 1 ).I(t - 1 )
iv. Elements with a "unit refractory period." An element will
be said to have a unit refractory period if, regardless of
other firing conditions, it cannot fire on two successive
moments. Thus if a con-junction N has a unit refractory
period, its behavior can be described by the equation
N( t ) = Aft - 1 ).B(t - 1 ).N(t - 1 ).
A tx1
B
A "net" composed of copies of a set ..., J. of elements will be de
fined as an assembly of such elements in ^hich output fibres of some elements
will be connected to input fibres of others. It is permitted to split any
output fibre into any number of fibres, but this is not allowed for input
fibres. A certain collection of input fibres S ^ ..., Sm will be dis
tinguished as "input fibres of the net" and similarly for some distinguished
collection . . ., Rn of output fibres.
A stimulus A^ is a finite set of firings of input fibres of the
net: thus A is a union of a finite set of events S (t ) (i = 1, ..., n )
3 oc a. a. a
l l
where S^(t^) means that fibre Sj_ fires at time t = t ..
A response of the net is defined similarly to be a union of
events R (t ) where R. (t.) means that fibre R. fires at time t..
J J
SOME UNIVERSAL ELEMENTS FOR FINITE AUTOMATA
119
(We will consider only nets which produce finite responses to finite stimuli.)
A response function f will be a finite pairing of stimuli with
responses; f: A^
---
Zf(a)‘ ma^ reSarcieci as operating
either on the stimuli or their index sets. )
In order to eliminate complications related to the question of ab
solute time it is convenient to restrict the domain of definition of a re
sponse function to some "admissible class of stimuli II," as follows:
A class II of stimuli is admissible if it has the property that if
A = j ^ (t^ ) j- is in II then for no k f- 0 is the stimulus Ak = j S^ ^ (t^ ^ + k )
also in II. Thus an admissible class contains no pair of stimuli which are
equivalent under time translation. It follows that the null-stimulus cannot
be a member of any admissible class. This restriction is very mild, since
unless a net has some kind of internal absolute clock it cannot be expected
to distinguish between time translated stimuli. If the net contains some
kind of cyclic activity with period p (and if a finite net contains perma
nent activity this activity must be essentially periodic) then it might dis
tinguish between time translations on a residue class basis; the definitions
might be extended to cover this case but it seems hardly worth while, at this
stage.
An example of an admissible class of stimuli which will be useful
later is the class IIa (b) containing all stimuli A for which
(ai)S±(a) e A.|s.(t) e A = ► a < t < a + bj
i.e., II (b) is the class of all stimuli whose first firing occurs at time
cl
a and whose total duration is not longer than b moments.
2 . Realization of Response Functions
In the general problem considered here we will be given a set of
elements J , ..., and also a response function f defined over some
admissible class of stimuli II. We are asked to construct a net out of
copies of the which will "realize" the given function. Now it may turn
out that this cannot be done. Consider the following example. It is easy
to show that if each of the elements of a net have a "monotonic" 1 response
function then so will the net as a whole. Then no non-monotonic response
function can ever be realized by any net composed of elements each of which
is itself monotonic.
1
A response function is monotonic If
A 1 C A 2 ==>. f(A 1 ) C f(A 2 ).
Thus "monotonic" means "weakly monotone increasing^set-theoretically."
MINSKY
In this example the non-realizability is due to a kind of basic
"functional" incompatibility between the given elements and the given func
tion. It may happen, however, that the failure of a class of nets to realize
a given function is due rather to trivial limitations on the "computation
speed" or "information channel capacity" of the elements, than due
directly to function-theoretic limitations. In order to maintain this distinctic
and not to discriminate too harshly against nets which are simply "too slow,"
the notion of "realization" of a function will be coupled with notions of
1lcomputation delay" and of "expanded time scale."
DEFINITION: Given a response function
will be said to "realize f with delay d"
function
f; Aa — Zf(a)' a net
if the net in fact realizes the
a
Zfd(a)
all
Aa c II
where
Rk (t)
6 Z = R(t - d) € z
i (a) k f(a)
DEFINITION:
f "in the p-expanded
Under the same conditions a net will be said to realize
time scale" if the net in fact realizes the function
p V
pZf(a),
S,(pt)
Rj(pt) 6 pZ
where
e A and
e Z.
If f is defined over an admissible class, then so are f , f
d
and (f ) etc. In the p-expanded time scale, both the stimuli and the
responses are stretched out uniformly in time. One can imagine a machine
with an input channel capacity so limited that the stimuli cannot be ab
sorbed at the given rate, but that if the signal is slowed down to match the
input capacity the given problem can be handled. Our main result is the
THEOREM: Given a response function f defined on
an arbitrary admissible class II of stimuli, there
are realizations of f^ (for some d) and of p^
(for some p > 0 ) in nets which contain only copies
of the following elements:
i. "dis-junctions" and "con-junctions."
ii. Any element J whose response function is
non-monotonic.
|Since it can be shown that any monotonic response function can be realized
in the form fd by a net composed only of con-junctions and dis-junctions,
condition ii. can be replaced by the condition
iif. Any element J which cannot be realized (with some delay)
by the elements of i .)
SOME UNIVERSAL ELEMENTS FOR FINITE AUTOMATA
The elements lil. and iv. of section 1. are examples of non-monotonic elements.
In the following proof of the above theorem, no effort will be made to mini
mize d and p where simplicity of proof would suffer. The proof will be
divided into several parts. Perhaps use of the "active loop" of C below
should be permitted explicity as an hypothesis.
A. CONSTRUCTION OF THE ELEMENT A net is constructed which iso
lates the non-mono tonicity of the element J. See Figure 1 .
Let J have m input fibres, n output fibres, and response
function fj. Since J is non-monotonic, there are two stimuli A 1 and A2
for which A 1 A2 but fjCA^ ) $ f^(A2 ). Then there must be an R^(t*) for
which Rk*(t*) e fJ(A1 ) and Rk*(t*) i fj(A2 ), where R^.* is some output
fibre of J. Assume that t = 1 is the time of the first pulse of A2
(otherwise time-translate A 1 and A2 and fj so that this will be the
case). Supply now two input fibres N 1 and N2 for the net, and for each
S^.(t) in A 1 run from N 1 a chain containing t-1 intermediate cells and ending
on an input fibre of a dis-junction attached to the fibre S^. of J. Do
the same for N 2 and each i-n A2 ' (NOTE: We shall not explicitly
limit the number of input fibres to con-junctions or dis-junctions to 2 ,
but will allow an arbitrary number. This can be reduced to the 2 - case by
the construction of simple sub-nets; the additional delays introduced
will lead to a higher value of "d" for the construction, but not alter in
any essential way the main lines of the proof.)
The stimulus N ^ O ) will cause the stimulus A 1 to be presented
to J, and likewise for N 2 and A2 . The stimulus N 1(o).N2(o) is equiva
lent to N2 (0 ) as far as J is concerned. Now supply a con-junction R*
with one input connected to R^.* and the other connected to the output of
N 1 through a chain of t* intermediate cells. Then the firing of R* will
represent the response function R*(t* + 1 ) = N1(o).N2(o), assuming that
pulses arrive at N 1 and/or N2 only at t = 0 . There is no telling what R T
will do if sequential stimuli arrive at the input. However since J is a
"finite network element", there is a certain time d(J) such that if no S^
is fired in an interval of this duration then J will revert to its resting
state. Let T(J) = d(J) + (time of latest pulse in A^). Supply a chain of
length T(J) - d(J) beginning with R f and ending on a final cell called
R^. Define the net to be the net so constructed and having N and N0
J
as input fibres and R as output fibre. This net will have the property
that it will act as though it were a b. i. j. with delay T(J) if it is
used in such a way that not more than one input firing time occurs within
any interval of duration T(J).
B. THE "SEQUENTIAL RESOLVER" NET. The first step in construction of the
realization net will be construction of a net N which will convert the
sequential patterns of stimuli into equivalent non-sequential patterns. In
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.