REPRESENTATION OP EVENTS IN NERVE NETS AND FINITE AUTOMATA1
S . C . Kleene
INTRODUCTION
1 . Stimuli and. Response
An organism or an automaton receives stimuli via its sensory re
ceptor organs, and performs actions via its effector organs. To say that
certain actions are a response to certain stimuli means, in the simplest
case, that the actions are performed when and only when those stimuli occur*.
In the general case both the stimuli and the actions may be very
complicated.
In order to simplify the analysis, we may begin by leaving out of
account the complexities of the response. We reason that any sort of stimu
lation, or briefly any event, which affects action in the sense that differ
ent actions ensue according as the event occurs or not, under some set of
other circumstances held fixed, must have a representation in the state of
the organism or automaton, after the event has occurred and prior to the en
suing action.
So we ask what kind of events are capable of being represented in
the state of an automaton.
For explaining actions as responses to stimuli it would remain to
study the manner in which the representations of events (a kind of internal
response) lead to the overt responses.
Our principal result will be to show (in Sections 7 and 9 ) that all
and only the events of a certain class called "regular events" are repre
sentable .
The material in this article Is drawn from Project RAND Research Memo
randum RM-70^ (15 December 1951, 101 pages) under the same title and by the
author. It is used now by permission of the RAND Corporation. The authorfs
original work on the problem was supported by the RAND Corporation during
the summer of 1951.
3
KLEENE
2 . Nerve Nets and Behavior
McCulloch and Pitts [19^3] in their fundamental paper on the logi
cal analysis of nervous activity formulated certain assumptions which we
shall recapitulate in Section 3.
In showing that each regular event is representable in the state
of a finite automaton, the automaton we use is a McCulloch-Pitts nerve net.
Thus their neurons are one example of a kind of "universal elements" for
finite automata.
The McCulloch-Pitts assumptions were put forward as an abstraction
from neuro-physiological data. We shall not be concerned with the question
of how exactly the assumptions fit. They seem to fit roughly up to a point,
though one of McCulloch1 s and Pitts* results is that certain alternative as
sumptions can explain the same kind of behavior. With increasing refinement
in the neuro-physiological data the emphasis is no doubt on respects in which
the assumptions do not fit.
Our theoretical objective is not dependent on the assumptions fit
ting exactly. It is a familiar strategem of science, when faced with a body
of data too complex to be mastered as a whole, to select some limited domain
of experiences, some simple situations, and to undertake to construct a
model to fit these at least approximately.
Having set up such a model, the next step is to seek a thorough
understanding of the model itself. It is not to be expected that all fea
tures of the model will be equally pertinent to the reality from which the
model was abstracted. But after understanding the model, one is in a better
position to see how to modify or adapt it to fit the limited data better or
to fit a wider body of data and when to seek some fundamentally different
kind of explanation.
McCulloch and Pitts in their original paper give a theory for nerve
nets without circles [Part II of their paper] and a theory for arbitrary
nerve nets [Part III]. The present article is partly an exposition of their
results; but we found the part of their paper dealing with arbitrary nerve
nets obscure, so we have proceeded independently there.
Although we are concerned with the model itself rather than its
application, a few remarks on the latter may prevent misunderstanding.
To take one example, as consideration of the model shows, memory
can be explained on the basis of reverberating cycles of nerve impulses.
This seems a plausible explanation for short-term memories. For long-term
memories, it is implausible on the ground of fatigue, also on the ground that
calculations on the amount of material stored in the memory would call for
too many neurons [McCulloch, 1949], and also on the basis of direct experi
mental evidence that temporary suppression of nervous activity does not cut
off memory [Gerard, 1953].
REPRESENTATION OF EVENTS IN NERVE NETS 5
The McCulloch-Pitts assumptions give a nerve net the character of
a digital automaton, as contrasted to an analog mechanism in the sense fa
miliar in connection with computing machines. Some physiological processes
of control seem to be analog. Just as in mathematics continuous processes
can be approximated by discrete ones, analog mechanisms can be approxjjnated
in their effect by digital ones. Nevertheless, the analog or partly analog
controls may for some purposes be the simplest and most economical.
An assumption of the present mathematical theory is that there
are no errors in the functioning of neurons. Of course this is unrealistic
both for living neurons and for the corresponding units of a mechanical auto
maton. It is the natural procedure, however, to begin with a theory of what
happens assuming no malfunctioning. Indeed in our theory we may represent
the occurrence of an event by the firing of a single neuron. Biologically
it is implausible that important information should be represented in an
organism in this way. But by suitable duplication and interlacing of cir
cuits, one could then expect to secure the same results with small probabil
ity of failure in nets con, trueted of fallible neurons.
Finally, we repe it that we are investigating McCulloch-Pitts nerve
nets only partly for theii own sake as providing a simplified model of nervous
activity, but also as an illustration of the general theory of automata, in
cluding robots, computing machines and the like. What a finite automaton
can and cannot do is thought to be of some mathematical interest intrinsic
ally, and may also contribute to better understanding of problems which arise
on the practical level.
PART I: NERVE NETS
3. McCulloch-Pitts Nerve Nets
Under the assumptions of McCulloch and Pitts [19^3 ], a nerve cell
or neuron consists of a body or soma, whence nerve fibers (axons) lead to
one or more endbulbs.
A nerve net is an arrangement of a finite number of neurons in
which each endbulb of any neuron is adjacent to (impinges on) the soma of
not more than one neuron (the same or another); the separating gap is a
synapse. Each endbulb is either excitatory or inhibitory (not both).
We call the neurons (zero or more) on which no endbulbs impinge
input neurons; the others, inner neurons.
At equally separated moments of time (which we take as the integers
on a time scale, the same for all neurons in a given net), each neuron of
the net is either firing or not firing (being quiet). For an input neuron,
the firing or non-firing at any moment t is determined by conditions out
side the net. One can suppose each is impinged on by a sensory receptor
organ, which under suitable conditions in the environment causes the neuron
to fire at time t. For an inner neuron, the condition for firing at time t
6
KLEE3ME
is that at least a certain number h (the threshold of that neuron) of the
excitatory endbulbs and none of the inhibitory endbulbs impinging on it
belong to neurons which fired at time t - 1.
For illustration, consider the nerve net shown in Figure 1, with
input neurons , K , % ,eM and erf, and inner neuron *P . Excitatory endbulbs
are shown as dots, and inhibitory as circles. The threshold of <P is 3,
as shown by the number in the triangle representing its soma. The formula
written below the net expresses in logical symbolism that neuron *P fires
at time t, if and only if all of , K and Sf and none of cM and J l fired
at time t - 1. We are writing "P(t)" to say that neuron P fires at time
t, ”J(t - 1)" to say that fired at t - 1, etc. The symbol
means if and only if (or is equivalent to), means and, nV 1t means or
(in the non-exclusive sense), and " " means not.
/T % cM erf £ £ % cM erf
P(t) = J(t - 1 ) & K(t - 1) & L(t - 1) P(t) = [[J(t - 1 ) & K(t - l)] V
& M(t - 1 ) & N(t - 1). [J(t - 1) & L(t - 1)] V [K(t - 1) &
& L(t - 1)]j & M(t - 1) & N(t - 1).
FIGURE l: Conjunctive Net FIGURE 2
P(t) s N(t - 1),
P(t) s L(t - 1 ) V M(t - 1 ) V N(t - 1 ). Q(t) = N(t - 2).
FIGURE 3: Disjunctive Net FIGURE Delay Net
k . The Input to a Nerve Net
Consider a nerve net with k input neurons J f , . . . , We as
sume k > 1, until 6.3. The input (or experience) over all past time up to
the present moment inclusive can be described by a table with k columns
REPRESENTATION OF EVENTS IN NERVE NETS
7
corresponding to the input neurons, and with rows corresponding to the moments
counting "backward from the present moment p. The positions are filled with
0*s and 1's, where 0 is to stand for quiescence, and 1 for firing, of
the neuron in question at the moment in question.
For example with k = 2 the table might be like Figure 5 . The
1 in the first row and first column means that J f fires at time p, the
0 in the third row and first column that did
t cM2 n°t fire at time p - 2, etc. If this table is ex-
p 1 0 tended down infinitely, we have a representation of
p - 1 1 1 the input, thought of as extending over all past
p - 2 o 1 time, which for the time being we treat as infinite.
(In Section 6 we shall reconsider the matter.)
FIGURE 5 By an event we shall mean any property of the
input. In other words, any subclass of the class
of all the possible tables describing the input over all past time (and ending
with the present p inclusive, except when otherwise stated) constitutes an
event, which occurs when the table describing the actual input belongs to
this subclass.
Examples of events with two input neurons J t and are:
(l ) J f fires at time p .
(2) does not fire at time p, and fired at time p - 1 .
(3) One of Xj and fires at time p.
( k ) and both fire at time p.
(5) ttfq fired at some time.
(6) e^2 fipe<3- at every time except p.
Of these, the input described by the table of Figure 5 constitutes an occur
rence of events (1), (2), (3) and (5), but not of (4 ), while we need to know
the rest of the table to know whether it constitutes an occurrence of (6).
5 . Definite Events
5.1 "DEFINITE EVENTS" DEFINED. We shall discuss first events which refer
to a fixed period of time, consisting of some i (> 1 ) consecutive moments
p - 1 + 1, ..., p ending with the present. We call such events definite of
length (or duration) 4 . Of the preceding examples, (1) — ( h ) are definite,
but not (5) and (6).
Then in a table such as Figure 5 we need consider only the upper
most 4 rows; e.g., that table for i> = 3 then describes an event also
described by the formula N ^p ) & Ng(p) & N ^ p - 1) & N2(p - 1) & N ^ p - 2) &
& N2(p - 2).
There are exactly k$ entries in a table describing the input on
k neurons for the i moments p - i + 1, . .., p. Therefore there are ex-
actly 2 possible such tables. Therefore there are exactly 2 definite
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.