1 22
M IN S K Y
CHAIN OF t* CELLS
CHAINS
FIGURE 1
computer language, the system Is to be converted from serial to parallel
operation, at the expense of duplication of machine components. Assume, for
the present, that the stimuli are in II (b); this will be generalized later.
a-p ^
The net N makes use of identical copies of the following net
CD
N^ , one for each input variable of the function to be realized.
SR
All cells in N^ are disjunctions except for the con-junctions
S ^ . The net has the property that if A e H Q(b) and if is fired only
at time A + b, then S^ ( 1 +A + b) = S^(j) e a. (The value of A will be
fixed later. ) Hence the sequential stimulus occuring in the interval
(0 , b - 1 ) is converted into a unit duration firing pattern on the S ^
The total net NSR is composed of the N1SR by tying all the
fibres Y. to the output of a single cell Y and connecting fibres from
each S^ to the input of a single dis-junction X. Between X and Y will
SOME UNIVERSAL ELEMENTS FOR FINITE AUTOMATA
123
go the "unit pulser", to be described in the next section.
The latter is the device which is supposed to produce the unit pulse at
t = A + b . Except for this the realization of the function f Is easily
completed. For each stimulus A
0 of II-(b) we supply three elements; a
J J
dis-junction E . and con-junction Fo and a copy Q of Q . For each
a a a
S.(j) in Ao connect a fibre from the output of S.^ to an input of E .
l a l • a
For each S. (j) NOT in connect a fibre from S . ^ to an input of Fo
l a 1 a
Connect the output of E^ to the input N- of I and the output of Fo
a I a a
to the input Nn of I . Then the following may be verified: If AQ is
J J
the stimulus, the only activity of the output cells Rq of the nets Qa
will be the firing of the single cell Rf at time (2 +A+b+T(J)), a
time which is independent of A e II (b). Now let the function to be real
ized be f: A^ — ^f(a)' Supply a bank of dis-junctions R^. of "final out
put cells." For each A& e n and each e Zf(a) run a chaln t - 1
intermediate cells from the output of Rf to an Input of Rv . 2 The resuitin
a k.
net, with the S^ taken as inputs and the R^ taken as outputs,can be seen
to realize the function
j^2 + A + b + T( J ) .
2 If there is an R]^(t) with t < 0 this could be realized here by In
serting a uniform delay at this final level; it would be reasonable to
rule out such an event as Inconsistent with the notion of causality.
MINSKY
C . CONSTRUCTION OF THE "UNIT PULSER." We have to construct a net which pro
duces a single pulse output in response to any stimulus of a given admissible
class, and such that the time of the pulse is independent of the particular
stimulus of the class. It will be shown that once a single pulse is avail
able it is not difficult to get the pulse to be independent of the stimulus.
But serious difficulties arise in constructing a device to get a single pulse
even without regard to the time of its occurrence. For such a device is
distinctly non-monotonic and must use copies of J. The non-monotonicity of
J can be extracted by the construction of a device such as the net But
this device, and presumably any like it, must be protected from receiving
closely spaced series of pulses (in general). Yet the "unit pulser" may be
regarded as a device whose precise function is to remove pulses from arbitrary
series of pulses until there is just one pulse left. Where can this reduction
of the number of pulses occur? It is easy to see that no monotonic network
can reduce the number of pulses in one given series without giving a null re
sponse to some other stimuli (e.g., to any single pulse input). Hence a net
like Qj? will ultimately have to receive the series of pulses, and protection
of its input by a non-monotonic net will just push the problem back to the pro
tection of the Q^*s or equivalent in the "protecting" net. It seems some
other technique must be invoked. First, one may take recourse to operating
the whole net in the T(J)-expanded time scale. Then the Q^'s will not
need protection, and the realization problem becomes simple for the function
T(J)f .
The problem can also be solved by the introduction of a permanently
active "closed loop" into the network. While this is done with reluctance,
it seems, In general, to be necessary. There are some important special cases
in which this can be avoided and those will be mentioned after the general
method is described.
The following net represents a complete "unit pulser." It has three
parts: See Figure b.
I A device for converting arbitrary stimuli of II0 (b) into the
standard form of unbroken series of pulses (the length of which
series may vary),
II A closed loop which acts as a periodic pulse source, and
III A network which makes the output of the assembly independent
of the phasing of the loop activity with respect to the stimulus.
All elements are dis-junctions except for a bank M. of conjunctions and
j 1
a bank of copies of Q .
The loop of cells (P1, P2, Pip(jj) assumed to contain one circulating
pulse so that P fires exactly once in any interval of duration T(J).
Operation of the net is as follows: The cells convert the input stimulus
pattern into an unbroken firing sequence at L 1 = . This train of pulses
propagates out along the and the leading pulse of the train remains in
SOME UNIVERSAL ELEMENTS FOR FINITE AUTOMATA
125
X = K , K2 K3 K4 ...K b
b-L1 L2 L3
P1 P 2 P3 P T (j )
n
-t (j )
) T k T H " I 1 1 T
- P m
IVL
2/ 2 / 2
M
' s r ' T ' 7r ir ' s r " s i
Qr*'* C>S*
QJ
N, N2 N3
m
r ( , ) = Y
the
the cell
Li ^or exactly
T(J) moments. At exactly one moment in this interval
P 1 fires and an image of the activity in the L^ is copied at
the M. level. This pattern is presented at the next moment to the bank of
T J
Q: units. Note that since no Q, can have been excited in the previous
J
T(J) - 1 moments, they are ready to act as b. i. j.!s. Exactly one
will now fire; namely the one which is exposed to the leading pulse of the
train. (At a time T(J) moments later, there may still be pulses in the
L., but the leading pulse will have left the bank of T ^ ^
can fire at this time
. J
The cells marked CT and C
L-cells and no
L
jjy^ prevent the end of
the L-bank from behaving like a leading pulse. ) Firing of one allows
one pulse to enter the bank N^ of cells. This bank adjusts the time of
arrival of the single pulse at the final output cell Y so that the time of
arrival is independent of the firing time of P I This time (for stimuli In
IIQ(b)) is exactly 1 + b + 2T(J). The ’’unit pulser" is complete. The
value of A is fixed by the relation A+b=l+b+2T(J) so that
A = 1 + 2T(J). The entire system now realizes the function
r>b+3+3T( J )
For operation in the T(J)-expanded time scale, first remove the
loop of the P^, Remove the bank of M1 cells and connect directly from
the output fibres of the
Li
to the corresponding inputs of the
Then
between every element of the net and its output fibre insert a delay chain
of length T(J) - 1 . In the expanded time scale the Q? 1s will not need
^ This construction involving the L, M, and Q elements was discovered
independently by Dr. L . S . Shapley.
MINSKY
the previous protection. After adjustment to a new value for A the net
will realize the function for some <3- of the order of magnitude
of b + 3 + 3T(J). It is not difficult to show how to modify the net so
that it realizes the function f for a p somewhat greater than the above
d. Smaller values of p and d could probably be obtained, but there is
no reason to try to find minimal realizations at this point.
It remains to extend the result to the general admissible class II.
Let b be the maximum duration of stimuli in II. Let t be the time of the
a
first pulse in the stimulus A& . Then if f : A& — ^f(a) S^-ven
function, define Aa*, and f* as follows:
Sy t ) € A* 3 y t + ta ) e Aa
Rj(t) e Zf(a) s Rj(t + ta ) € Zf>(a),
f.; A| ^ Z f ( a ) .
Then A* is in II. (b) for all A^ In II. And because II is an admis-
cL U cl
sible class, A^ /= A, =>- A* /= A,*. The function f* can then be realized
S D cl D
as shown above. But the response function of the net constructed for the
realization of f* is invariant under time-translation of input and output.
Hence the net which realizes f* must also realize the given function f .
This completes the proof.
3 . Special Cases
For certain elements, realization of arbitrary functions can be
achieved without recourse either to the expanded time scale or the loop de
vice. A simple instance is that of the "binary inhibitory junction" of
section 1 . In this case T(J) = 1 so that realization in the T(J)-scale
is realization in the ordinary time scale. A more interesting case is that
of the cell with unit refractory period. It is actually possible to realize
arbitrary functions in the ordinary time scale with nets composed entirely
of con-junctions and dis-junctions each of which has a "unit refractory
period" (or any longer period), provided only that we are supplied with banks
of input and output cells which do not have this limitation, (an obviously
necessary condition), and it is not necessary to use the loop device. The
proof is much too specialized to present completely, but the method may be
of interest. The net is similar to the previous constructions except in two
respects; first the main net I is split into two identical halves and a de
vice is introduced which shifts the stimulus pulses alternately between the
halves so that each half can operate in the 2-expanded time scale. Instead
of the loop device, the following net Is introduced, for stimuli in IIQ(b):
This net produces exactly one output pulse for any stimulus in IIQ(b); the
reader is encouraged to trace through its operation to see how this is done.
Remember that no element can fire on two successive moments. The time of
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.