Aiserman M., Gusev L., Rozonoer L., Smirnova l., Tal A. Logic, Automata, and Algorithms
Подождите немного. Документ загружается.
110
ELEMENTS
OF
MATHEMATICAL
LOGIC
where
h
is
a
given finite number, called the
thveshold
of
stimulation.
A
neuron
is
not stimulated unless these conditions
are
met. Thus
the inhibitory ending has “veto power”; that is, even
if
inequality
(4.36)
is
satisfied, the output
is
not stimulated
if
the input of the
neuron in question
is
connected
to
even one inhibitory branch of
a
stimulated neuron.
*
Fig.
4.19.
If
u,
is
the state of the simple input fibers
(i
=
1,
2,
. .
.,
s),
vI
is
the state of the inhibitory input fibers
(j
=
1,
2,
. .
.,
q),
and
x
is
the
state of the neuron, then the behavior of
a
McCulloch-Pitts neuron,
such that
s
=
3,
h
=
2,
q
=
2
is
described by
Let us mark off points
0,
T,
27,
37,
.
.
.
on the time
axis
and observe
the neurons and neural nets only at suchinstants; that is, let us in-
troduce sampling instants. Instead
of
0,
‘I,
27,
37,
.
.
.
we
introduce in-
tegers
0,
1,
2,
..
.,
P.
..
respectively, to denote the occurrence
of
these sampling instants. Then expression (4.37) may be written
as
(4.38)
Now consider any McCulloch-Pitts abstract neural net consist-
ing of
n
neurons and having
s
‘‘free” inputs, through which external
effects can be introduced. We shall label the neurons contained in
the net by
1,
2,
. .
.,
11
and the
free
input fibers by
1,
2,
.
.
.,
s;
we
shall
also denote by
xi
the state of the ith neuron and by
uj
the state
of the jth input fiber of the net. Then
we
can write
n
equations of
the form (4.38). Eachinput of aneuron
of
the net
is
acted upon either
*Frequently, other conditions
for
the functioning
of
neurons are specified
(see,
for
ex-
ample,
[73]).
ABSTRACT
NEURONS
AND
MODELS
OF
NEURAL
NETS
111
by the ending of one of the other neurons
or
by an external effect.
Therefore each
w
or
v
can be identified with an
x
or
a
u;
that
is,
we
can introduce
xp
or
upinto the right-hand sides of expressions (4.38),
to replace
WP
and
UP,
respectively.
It follows from the foregoing that the McCulloch-Pitts abstract
neural net can be described by the system of relations
xp+’=
L,(Xf,
“k,
.
.
*,
xg;
uf,
q,
.
.
.,
Uf).
i=l,
2
,...,It,
(4.39)
where
Li
are
logical functions such
as
(4.38).
Thus, the McCulloch-Pitts abstract neural net
is
in effect
a
net
according to
our
definition of this term, and
is
therefore
a
finite
automaton. But since the right-hand side of (4.39) contains not
just
any logical functions but functions of a special type [the (4.38) type],
there
arises
a question: Canwe construct aneural net to correspond
to any given finite automaton operating in the
0,
1,
2,
, ,
.
(that is,
0,
T,
27,
. .
.)
timing sequence?
To
answer this question,
it
will
be pointedout, first of
all,
that
a
self-simulated neuron with
h
=
1
and
no
inhibiting inputs (Fig.
4.20)
is
a
blocked,
or
permanently simulated, neuron. Therefore
neurons may have permanently stimulated inputs (Fig. 4.21,a), de-
noted
as
shown in Fig. 4.21,b.
We
shall say in this case that the
stimulated input fiber
is
fixed.
We
shall now consider a neuron with
h
=
1,
s
=
1,
and
9
=
0
(Fig. 4.22).
Such a
neuron
is
described by
xP
tl-
-
wp,
that is, one neuron
will
produce
a
delay
Fig.
4.20.
Fig.
4.21.
of
one sampling instant. By connecting
9
such neurons in series
(Fig. 4.23),
we
can produce
a
delay
of
9
sampling instants.
112
ELEMENTS
OF
MATHEMATICAL LOGIC
Fig.
4.22.
Fig.
4.23.
Consider now
a
neuron
for
which
h
=
I,
s
=
1,
q
=
1,
and fix the
input stimulus (Fig. 4.24). Then the neuronembodies the relationship
-
xP+l-
P
-v,
that
is,
the single neuron performs the operation
of
negation with
a
delay of one instant.
A
neuron for which
h
=
1,
q
=
0,
and
s
is
any number (Fig.
4.25)
is
an embodiment of a disjunction
of
s
variables with a delay
of
one instant:
x~+~=w;vwg/
I..
vwg,
while a neuron with
h
=
s
(for
any
s)
and
q
=
0
(Fig. 4.26)
is
an em-
bodiment of
a
conjunction of
s
variables with
a
delay of one instant.
Fig.
4.24.
Fig.
4.25.
If
we
desire
to perform a conjunction of
s
variables, some
of
which are negated, then the negated variables must be introduced
at
the inhibitory inputs
while
h
must equal the number
of
negated vari-
ables. Thus,
for
example, the conjunction
can be embodied by
a
single neuron, as shown in Fig.
4.27.
ABSTRACT NEURONS
AND
MODELS
OF
NEURAL
NETS
113
Fig.
4.26.
Fig.
4.27.
Consider now an arbitrary disjunction of conjunctive groups. Let
such
a
disjunction contain
rn
groups. Then each conjunctive group
may be performed by
a
single neuron in accordance with Fig. 4.27.
The outputs of these neurons
are
connected to
a
neuron which per-
forms the disjunction (Fig. 4.25). Since
all
the
neurons performing
conjunctions
c'fire99
during one instant, and since just one additional
instant
is
required for performing
a
disjunction, the entire disjunc-
tive formmay be performedin twoinstants, that
is,
in time
2~.
Thus,
Fig.
4.28.
Fig.
4.28 shows anet consisting
of
McCulloch-Pith neurons and
em-
bodying the form
Since any logical function may be presented
as
a
disjunction of
conjunctive groups, it can be performed over two sampling instants
by an abstract net consisting of McCulloch-Pitts neurons. Thus any
114
ELEMENTS
OF
MATHEMATICAL
LOGIC
logical converter
L
may
be
constructed from McCulloch-Pitts neu-
rons, but,
in
contrast to our usual assumptions, such a converter
will
not be instantaneous, because it
will
require two sampling in-
stants to finish its operation.
Assume now that the inputs vary
and that the state of the netis observed
at instants
0.
2-,
37,
.
.
..
With such
a
timing, one can construct
a
net
of
Mc Culloc h- Pit t
s
neurons that per
-
forms any logical conversion over
a
single sampling instant. Also, neurons
may be employed to form
a
delay
ele-
ment for such a “doubled” timing; to
do this
(see
Fig.
4.23),
two
delay
ele-
ments
are
connected in
series.
Now,
having
a
logical converter performing
any
desired
conversion and having
a
delay element,
we
can construct
a
net
embodying any desired automaton op-
erating with such
a
timing.
In Chapter 10
we
shall
consider
Fig.
4.29.
methods for synthesizing automata
operating with any desired “slow)’
timing, starting from elements operating with “fast” timing, pro-
vided the synchronizing signals for the occurrence of the “slow” tim-
ing are supplied from an outside source. We
shall
show that to syn-
thesize such systems
we
needelements capable of producing
a
delay
for
any such externally supplied timing.
To finish the discussion of neural nets,
we
shall
show how such
a
delay element may be synthesized from McCulloch-Pitts neurons.
Thus let us construct a net (Fig. 4.29) that performs, over time
27,
the function
-
,p+2=(.u?:’Sr.u?~)V(~~&.zer~).
We
combine
two
such nets into one net with two inputs
(u
and
ut),
as
shown in Fig. 4.30. The input
u
is
the basic input of the net,
while
I/[
is
used for introduction of
a
synchronizing signal (it
is
assumed
that the next sampling instant occurs when
uf
changes from
1
to
0).
Figure 4.31 shows
the variation of
x
and
xI
for some variations
of
li
and
lit.
The value of
x
coincides with the value
of
u,
but with
a
delay
of
one sampling instant. The net
will
function correctly
pro-
vided signals
i~[
follow each other at intervals not shorter than
4.c.
The
arrows in Fig. 4.31 bracket intervals
2:.
ABSTRACT
NEURONS
AND
MODELS
OF NEURAL
NETS
115
I
I
Fig.
4.30.
Fig.
4.31.
Thus, having
a
delay element
for
any external synchronizing
source,
as
well
as
a
converter “firing” in
the
time
2~,
one can, with
the
aid of the methods
of
Chapter
10,
use
McCulloch-Pitts neural
nets to embody any automaton
(or
sequential machine) with any de-
sired timing, provided
a
single condition
is
satisfied: the interval
between sampling instants cannot be shorter than
4.c.
5
Technical Embodiment
of
Finite
Automata
and Sequential Machines
5.1.
TWO METHODS FOR TECHNICAL REALIZATION
OF
FINITE
AUTOMATA AND SEQUENTIAL MACHINES
In the preceding chapters
we
have formally introduced the con-
cepts of “finite automaton,’’ “sequential machines,” and “abstract
structure.”
So
far,
these
were
presented only
as
equations or sys-
tems of equations, and
we
did not deal with the physical nature of
the dynamic systems whose motion they describe. Now
we
shall
show that
the
above concepts describe important technical systems,
and we
shall
introduce techniques for determining the hardware
needed for realizing any given
finite
automaton or s-machine.
We
have
shown in Chapter
4
that each finite automaton-or
S-
machine may be represented by many abstract structures. But each
abstract structure may
be
embodied by some practical device that
functions just
like
this abstract structure.
It
follows that any finite
automaton can have many technical embodiments.
We
shall also show
that any given abstract structure of any given automaton may be em-
bodied (realized) by many technical means.
In this chapter
we
shall consider only embodiments (realiza-
tions) of binary abstract structures; that
is,
it
will
be
assumed
that the finite automaton
is
given by
a
system of relations
X?+’
=
Fi
[x:,
x;,
. .
.,
x;,
u?,
UP,
.
.
.,
US^]
(i
=
1,
2,
.
.
.,
n),
(5.1)
where
xi
(i
=
1,
2,
.
.
.,
n)
and
IL~
(j
=
1,
2,
.
.
.,
s)
arelogicalvariables
which can be only
0
or
1,
and
Fi
(i
=
I,
2.
. .
.,
n)
are
logical functions,
which
also can be only
0
or
1.
We
also assume that the timing of
the automaton
is
given, that
is,
we
aregiven the conditions defining
the
occurrence of the
discrete
moments
0,
I,
2,
. .
.,
p
on
the
con-
tinuous time scale.
116
AGGREGATIVE DESIGN
OF
FINITE AUTOMATA
117
To
produce
a
technical device performing relation (5.1), one must
have logical converters performing the functions
Fi.
We
have already
described such devices in Chapter
2.
Now, however,
we
do not want
to perform functions
Fi
themselves, but want to embody relations
(5.1) of
which
such functions
are
a
part. Thus,
we
are
faced with
the question: What modification must be introduced into the func-
tion converters of Chapter
2
(or
with
what must these converters
be supplemented), in order to transform them into devices whose
states
shall vary in time
so
as
to model the abstract structure (5.1)
?
We
shall now present
two
essentially different methods for solv-
ing the above problem.
5.2.
AGGREGATIVE DESIGN
OF
FINITE AUTOMATA
AND SEQUENTIAL MACHINES
We
already know that an abstract structure such
as
(5.1) can be
placed into correspondence with
a
structural diagram. Such
a
dia-
gram (for
n
=
3,
s
=
2)
is
shown in Fig.
5.1.
The diagram contains
s
input lines (input
wiresul,
up,
.
.
.,
us)
and
n
output lines (their co-
ordinates
are
states
xI,
x2,
.
.
.,
x.).
Each of thenlogical converters
performing functions
F,,
F2,
.
.
.,
F,,,
respectively, receives signals
from
all
the
n
+
s
lines;
the output of the ith converter feeds the
line
xi
via
a
one-instant delay element (denoted by a circle in Fig.
5.1),
whose output and input
are
related by
Direct examination shows that such
a
circuit models precisely
the structure of relations (5.1). To construct
a
technical device
ac-
cording to this diagram, one must have one-instant delay elements
in addition to the requisite logical converters.
Thus in order to
convert
a
set of elements sufficient for
the
embodiment of any logi-
cal
function into
a
set of elements sufficientfor
the
realization
of
a
finite
automaton, one needs only to supplement the first set with
a
single element-a one-instant delay element.
Such
a
set
is
also sufficient for the construction of any sequen-
tial
machine, since the latter
differ’s
from
an
automaton only in
having an output logical converter.
A
one-instant delay element must have
two
inputs-the basic in-
put
xin
and
an
auxiliary (time) input
xl.
It also must have an output
xout.
The conventional notation for such an element
is
shown in
Fig.
5.2.*
The auxiliary (time) input receives the signals indicating
*One usually omits the input
wire
xs
whenever such an omission does
not
hinder the
understanding
of
the operation
of
the
circuit.
118
ELEMENTS
OF
MATHEMATICAL LOGIC
Fig.
5.1.
the
occurrence
of
the
next discrete
mo-
ment, such signals being supplied to the
automaton
from
an external signal-pro-
ducing device
(a
“clock”
or
“synchro-
nous source”).
The delay element operates in the
following manner:
let
xy,
be the state
of
the input to the element at the first
discrete
moment. Then,
after a
short
p“
Fig.
5.2.
time interval
T
(the specific delay
of
the delay element), the output
shows
xour
=
x:~.
I1
I
I
I
I
cycle number
XLtlh
I
I
I
1
1
I
!--I
I
I
1
1
I
0
i
I
I
i
i
i?
Fig.
5.3.
After
this,
regardless of what happens at the input, the output
will
retain
its
value until
the
next
discrete
moment, when
the
same
procedure
is
repeated. The delay element does not
react
to any
changes occurring at the input during the time interval between
the
discrete moments.
AGGREGATIVE DESIGN
OF
FINITE
AUTOMATA
119
Figure
5.3
shows an example of changes occurring
at
the
input
and output
of
a
one-instant delay element. In this example the syn-
chronizing signals
are
short pulses. However, the synchronizing
signal often
is
each change of state
of
the auxiliary input, which can
also have only
two
values:
it
can be
either
1
or
0
(Fig.
5.4)
or,
al-
ternatively, it can only change from state
0
to state
l
(Fig. 5.5).
Consider the construction of
a
pneumatic one-instant delay
ele-
ment. Such an element
is
based on so-called memory cells. Sche-
matic diagrams of
two
types
of
memorycell
are
shown in Figs. 5.6,a
and b, respectively, where
the
change of state of the “time input”
Pt
from
0
to
1
serves
as
the synchronizing signal.
A
memory
cell
consists of
two
pneumatic relays
(see
Section2.4). One of these (the
output)
is
connected
so
as
to perform
a
“repetition,” maintaining
the output pressure
P
of the
cell
equal to pressure
Ph;
the other
re-
lay (the input) performs the function of
a
pneumatic valve, opening
or
closing
the
connection between
the
chamber
where
the pressure
Ph
is
established and the input lineP,. The operation
of
the pneu-
matic valve
is
governed by the pressure
Pt;
in
the
cell
of the
first
type
(Fig. 5.6,a) the valve
is
closedwhen
Pt
=
1
and open when
Pt
=
0,
and, conversely, in the cell of the second type (Fig. 5.6,b) it
is
closed when
Pt
=
0
and open whenP,
=
1.
Because of this arrange-
ment, either the
cell
output
is
equal to its input (for the first cell
when
Pt
=
0,
and
for the second cellwhenPt
=
I),
or
the output
is
not
connected with the input andis constant (in the first
cell
when
Pt
=
1,
and in the second
cell
whenP,
=
0)
,its value being determined by the
magnitude of the pressure
Ph
in the dead-end chamber.
A
memory
cell
of the
first
type connected in
series
with
a
cell
of
the second type constitutes
a
one-instant delay element (Fig.
5.6,~). This element operates in the following way: at
t,,,
when
Pt
is
1
(the beginning of the nthdiscrete moment), the first
cell
“mem-
orizes” the value of the input, that
is,
P*(f,)
=
P!(f,,).
In the same
instant (more precisely, at time
t,
+
At,
where the increment
At
is
caused by
the
fact that the working membrane
of
the second memory
cell
must travel
a
longer path than thatin the first one), the second
memory
cell
transfers the value rememberedby the first
cell
to the
output of the system: the pressure
P(f,)
=
P*(t,,)
=
P,(f,)
is
thus
established at the output of the delay element. After
this,
as
long
as
Pt
=
I,
there can be no changes in
the
system, since its state
is
de-
termined by the fact that throughout
all
this time the
first
cell
“re-
members” the input value
Pl(t,).
This means that
P(t)
=
P*(t)
=
PI
(fn)
when
in
,<
t
,<
t,,
where
ti
is
the instant at which
Pt
becomes
0.
At
time
ti
(see
Fig. 5.6,d) the input
to
the second memory cell
is
P(tL)=P,(t,);
the
cell
“memorizes” it, and there
is
thus no