28
KLEENE
as a disjunction of terms of the two kinds. Now consider E s; by taking
the disjunction for E given by the hypothesis of the induction, and multi
plying out ((6) and (7)), we obtain a sum of products of s factors each
as in Case 2 we obtained a sum of products of 2 factors each. A product in
which the factors are all of the first kind can be reconstituted as a unit,
which will be of length > s since the number of the factors is s, so it
becomes of the second kind. All other types of products which can occur
include a factor of the second kind, so by the treatment of the three types
of products E"Ft!, E"F* and E'F" under Case 2 (repeated as necessary),
each of these becomes of the second kind. So E s (after suitable reconsti
tution of units) becomes of the second kind. Now by the treatment of the
two types of products E"Fn and E"F* under Case 2,
E S(F V EF V E 2F V ... V E S_1F) and hence ES*ES(F V EF V E 2F V ... V E S_1F)
become of the second kind.
LEMMA 6. Each regular expression is reducible with
out reconstituting the units to a disjunction of one
or more terms of the form E^F^ where each E^ is
a unit and F^ is empty (then E^F is E^) or
regular (then E^ is non-initial).
PROOF. For a regular expression G of the second type of Lemma one can
see, by induction on the number n of units in G, that G can be trans
formed (using only ( k ) , (6), (10)) into a disjunction of terms of the two
kinds for Lemma 6.
7 .3 REPRESENT ABILITY OF REGULAR EVENTS. A k x £ table is prepositive
(positive), if it describes a prepositive definite event 6 . k , i.e., if it is
not initial and either £ = 1 or there is a 1 in its lowest row (a posi
tive definite event 5.1, 6.3, i.e., if there is a 1 in some row). A set
of tables is prepositive (positive), if every table of the set is prepositive
(positive).
THEOREM 3. To each regular event, there is a nerve
net which represents the event by firing a certain
inner neuron at time p + 2, when started with suit
able states of the inner neurons at time 1. If the
event is describable by a prepositive and positive
regular set of tables, the representation can be by
a net started with all inner neurons quiet.
PROOF. We begin by establishing the theorem for a regular event described
by a term G of the second kind for Lemma 5 with s = 2. We use induction
on the number n of units in G.
REPRESENTATION OF EVENTS IN NERVE NETS
29
We will arrange that the neuron (call it the output neuron)
which is to fire at p + 2 exactly if the event occurs ending with time p
shall be of threshold 1 Impinged on by only excitatory endbulbs (as in
Figure 3 ) , and shall have no axons feeding back into the net.
BASIS: n = 1 . We construct a net to represent (the event described
by) G by the method of proof of Theorem 1 Corollary 1 if G is prepositive
(a fortiori positive, since £ > s > 1 ), and otherwise this with the first
method of 6 A (with a neuron of Figure 16 or Figure 19) which makes the
event prepositive (so positive) as an event on k + 1 neurons, so the repre
sentation is by firing at time p + 2 in both cases.
INDUCTION STEP: n > 1 .
CASE 1 : G is E V F. By the hypothesis of the induction, there
are nets which represent E and F, respectively, each in the manner de
scribed, say with respective output neurons P and Q. To represent E V F,
we "identify" P and Q, i.e., we replace them by a single neuron (call it
P ) having all the endbulbs which Impinged separately on P and on Q; and
of course we similarly identify the input neurons N 1 , . N^.. The resulting
net is diagramed in Figure 2 2 . The box marked £ stands for the net for E
except for its input neurons and output neuron. The heavy line leading to
P from this box represents the axons which formerly led to the output neuron
*P in the net for E.
CASE 2 : G is EF. Consider the expression E* which is obtained
from E by altering each unit to make it refer to one new input neuron
^ k +1 required to fire at the second moment of each earliest unit (but other
wise not affecting the occurrence or non-occurrence of the respective definite
events); by the hypothesis that the units are of length > 2 , there is a
second moment. Then E T is of the second kind for Lemma 5 with the same
number of units as E, since the alteration gives a regular expression with
the same structure in terms of its respective units under the three opera
tions. So by the hypothesis of the induction we can represent E* and F by
nets as described. However we simplify the construction by leaving out the
neuron of Figure 16 in the case of each earliest non-prepositive unit of E f
(this unit is non-initial, by one of the properties of G secured in Lemma 5 ).
Now the net for EF is obtained by identifying the new input neuron ^-+1
in the net for E 1 with the output neuron Q of the net for F, besides
of course identifying the input neurons X, , ..., for the two nets, and
taking as output neuron the output neuron for E* (Figure 23). The
event E* is positive, since «^.+1 is required to fire at its second moment.
No hallucination is possible as a result of leaving out the neurons of
30
KLEENE
Figure 16 for earliest non-prepositive units of E*, since e/^+i (required
for those units to fire at their second moment) cannot fire until two moments
after an occurrence of F, by the construction of the net for F. These
omissions of neurons of Figure 16 are to give the last statement of the theorem.
CASE 3 : G is E*F. The nets for E* and F are combined as in
Figure 2 k .
FIGURE 22 E V F
FIGURE 23 EF
FIGURE 2k E*F
CONCLUSION. This completes the induction to show the representa-
bility of a regular event described by a term G of the second kind for
Lemma 5 with s = 2. Terms of the first kind are treated as under the basis
(but using Figure 16 additionally in the case with & = 1 of a prepositive
non-positive term), and the disjunction of terms (if there are more than one)
as under Case 1. The case the event is I has already been treated in
Section 5 (Figure 8).
DISCUSSION. If the original regular expression for the event is
already in terms of units each of length > 2 , the proof of the theorem is
straightforward and yields nets of complexity corresponding very well to
that of the regular expression. (For simplification of the nets representing
the units, possibly at the cost of increasing the lag above 2, cf. the dis
cussion following Theorem 1 Corollary 1 . ) The difficulty which calls for
complicated reformulation via the proof of Lemma 5 arises when we try to com
bine in succession the representations of events some of them shorter than
the time necessary for the net to organize a representation of the preceding
event by the firing of a single neuron; the solution by Lemma 5 consists in
considering grosser events before trying to combine the representations.
THEOREM k . To each event constructed from regular
events by the operations &, V, — , there is a nerve
net which represents the event by firing a certain
REPRESENTATION OF EVENTS IN NERVE NETS 31
inner neuron at time p + 2 , when started with suit
able states of the inner neurons at time l .
The proof will follow. By Corollary Theorem 5 below, all repre
sentable events are regular. So by Theorems 4 and 5 together, combinations
of regular events by &, V and are regular, which with Theorem 3 in
cludes Theorem U . We have not defined & and as operations on sets of
tables, so EF and E*F cannot be used after the application of & or .
PROOF OF THEOREM k . To each of the regular events which enter in the con
struction by &, V and of the given event, consider a regular expression
for the regular event. Apply to this Lemma 5 with s = 2 , and to the re
sulting terms of the second kind Lemma 6 . Thus we obtain an expression for
the given event by the operations &, V and — from components
E.F, , ..., E F where each E. is an expression for a definite event and
1 1 m m 1
F^ is a regular expression (then the definite event expressed by E^ is
non-initial and of length > 2 ) or empty. Let E| come from E^ as E'
came from E in the'proof of Theorem 3 Case 2 if F^ is regular, and be
the result of introducing an extra input neuron j l ^ + ^ to fire at the first
moment of E| if F^ is empty. Now consider (as an event on the k + m
neurons , . . ., , . . ., same combination of Ej, . . ., E^
as the given event is of ..., EmFm . If this combination of
Ej, ..., E^ when treated as a definite event in the sense of Section 5 (not
Section 6 ) of length equal to the greatest of the lengths of E] , ..., E^
is not positive, we make it so by adding "& E 1 1" where E ' m+1 refers
to the firing of a neuron ^ - +m+-| time p. Now use the method of net
construction for Theorem 1 Corollary 1 to construct a representing net for
this event on k + m or k + m + 1 neurons. Then for each i for which
F^ is regular, identify with the output neuron of a net given by
Theorem 3 representing F^; and for each i for which F^ is empty make
^k+i an inner neuron required to fire at time 1 , as in Figure 1 6 if E^
is non-initial or i = m + 1, and as in Figure 19 if E^ is initial.
7.^ PROBLEMS. Numerous problems remain open, which the limited time we have
given to this subject did not permit us to consider, although probably some
of them at least can be solved quickly.
Is there an extension of Theorem 1 Corollary 2 to all regular events
By the complete set of tables for an event we mean the set of tables
all of them initial which describes the event. By the minimal set of tables
for an event we mean the set of tables describing the event each of which has
the property that neither a proper upper segment of it, nor itself if it is
initial, as a non-initial table describes an occurrence of the event. The
complete set of tables for a regular event is regular, by Theorem 3 and the
32
KLEENE
proof of Theorem 5 . Is the minimal set necessarily regular? If so, can a
regular expression for it be obtained effectively from a regular expression
for the complete set?
What kinds of events described originally in other terms are regu
lar? We have only some examples of translation from (A) to (B) (end 7.1),
and one of an Indirectly established closure property of regular events
(Theorem k with Theorem 5 ).
Given a regular expression for an event, it may be difficult to
see of what the event consists. We know cases in which a very complicated
regular expression is equivalent to a much simpler one, e.g., some arising
via the proof of Theorem 5. Are there simple normal forms for regular ex
pressions, such that any regular expression is equal, or is equivalent, to
one in a normal form? Is there an effective procedure for deciding whether
two regular expressions are equal, or are equivalent?
Our reason for introducing the regular events, as given by regular
sets of tables described by regular expressions, is Theorem 5 , which we dis
covered before Theorem 3. By using the notion of regular events, we thus
demonstrate that a McCulloch-Pitts nerve net can represent any event which
any other kind of finite digital automaton (in the sense to be developed in
detail in Section 8 ) can represent. This of course includes a number of spe
cial results which McCulloch and Pitts obtained for alternative kinds of
nerve nets, but is more general. The way is open to attempt similarly to
verify the like for other kinds of "cells" in place of neurons, or to seek
some characterization of the properties of the cells in order that aggregates
of them have the capacity for representing all representable (i.e., all regu
lar ) events.
PART II. FINITE AUTOMATA
8 . The Concept of a Finite Automaton
8.1 CELLS. Time shall consist of a succession of discrete moments numbered
by the positive integers, except in Section 10 where all the integers will be
used.
We shall consider automata constructed of a finite number of parts
called cells, each being at each moment in one of a finite number > 2 of
states.
We shall distinguish two kinds of cells, input cells and inner cells.
An input cell admits two states, 0 and 1 (or "quiet" and "fir
ing"), which one is assumed at a given moment being determined by the environ
ment .
The restriction to 2 states for input cells makes the notion of an
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.