ACKNOWLEDGMENTS

This work was supported in part by the U.S. Army Signal Corps, the

Air Force Office of Scientific Research, and the Office of Naval Research; and in part by National Institutes of Health.

Section I is an introduction taken almost exclusively from the work

of Dr. Warren S. McCulloch. I wish to thank him, Herman Berendsen,

Jack Cowan, Gene Prange, Leo Verbeek, and my brothers Simon, George, and Michael, without whom this work would never have been completed.

REFERENCES

1.

2.

Warren S. McCulloch, "What is a Number, that a Man May Know It, and a Man, that He May Know a Number?", Ninth Annual Alfred Korzybski Memorial Lecture

of March 12, 1960, to be published in The Journal of the Institute of General Semantics.

Warren S. McCulloch, "The Stability of Biological Systems," in Brookhaven

Symposia in Biology No. 10. Homeostatic Mechanisms, (May, 1958), pps. 207-215,

available from the Office of Technical Services, Department of Commerce,

Washington 25, D.C.

3. Warren S. McCulloch, "Biological Computers," I. R. E, Transactions of Electronic Computers, Vol. EC-6, Number 3, (September, 1957), pps. 190–192.

4. Warren S. McCulloch, "Agatha Tyche of Nervous Nets

The Lucky Reckoners,

in National Physical Laboratory Symposium No 10. Mechanization of Thought

Processes, 2 vols. (London, 1959), II, 613-633.

5. Warren S. McCulloch, "Infallible Nets of Fallible Formal Neurons,

Quarterly

Progress Report of Research Laboratory of Electronics, M. I. T., (July, 1959), pps. 189-196.

6. E. F. Moore and C. E. Shannon, "Reliable Circuits Using Less Reliable Relays," Journal of the Franklin Institute, Part 1 in Vol. 262, (September, 1956),

7.

8.

pps. 191-208, Part 2 in Vol. 262, (October, 1956), pps. 281–297.

John Von Neumann, "Probabilistic Logics and the Synthesis of Reliable Organisms

from Unreliable Components," in Automata Studies, ed. C. E. Shannon and

J. McCarthy, (Princeton, New Jersey, 1956), pps. 43-98.

Charles Sanders Peirce, Collected Papers, ed. of Vols. 1-6, Charles Hartshorne and Paul Weiss. ed. of Vols. 7,8. Arthur W. Burks (Cambridge, Massachusetts,

1932, III, IV - 1933, V - 1934, VI - 1933, VII, VIII – 1958),

Vol. IV, pps. 13, 215-216.

RELIABLE COMPUTATION WITH UNRELIABLE CIRCUITRY +

L.A.M. Verbeek

Massachusetts Institute of Technology

INTRODUCTION

To give an outline of the structure of redundant networks composed from unreliable formal neurons resulting in reliable logical computation, a short description of the components and their properties is necessary.

A formal neuron is an all-or-none threshold device with many input lines and one output line. Each line can be in one of two possible states, 'on' or 'off'. The activity of the formal neurons is discrete in time which means that a finite unit of time elapses between consecutive states; we will not look into the timing but consider this as ideal. Input lines can have a positive connection or a negative connection with the formal neuron, this is to say that input lines in the 'on' state excite the formal neuron with a strength +1 or -1, and in the 'off' state with a strength 0. Positive connections will be indicated by arrows and negative connections by small zeros at the input lines of formal neurons. If the algebraic sum of the excitation of the input lines equals or exceeds a given value-the threshold -the formal neuron fires, giving rise to the 'on' state of its output line. Such a formal neuron is capable of logical computation. Figure 1 gives an example of a universal element or polypheck (ref. 1) consisting

Figure 1. Polypheck with two input lines (A and B) computing the
Sheffer stroke function X also indicated by the truth
table.

+This work was supported in part by the U.S. Army (Signal Corps), the U.S. Air Force (Office of Scientific Research, Air Research and Development Command), and the U.S. Navy (Office of Naval Research); and in part by The Teagle Foundation, Inc., and the National Institutes of Health.

of a formal neuron with two input lines computing a Sheffer stroke function given by the Venn diagram (ref. 2) drawn inside the formal neuron and also given by the truth table representation. Only part of all possible 22n logical functions of n input lines can be computed by a single formal neuron, others have to be computed by some simple neuronal network consisting of several appropriately interconnected formal neurons.

In an attempt to make these formal neurons and neuronal networks a model for the central nervous system, or for hardware automata, an important step is to consider possibilities of malfunction of the formal neurons and their interconnections, and the impact of these on neuronal networks. The next step is to investigate application of redundancy in networks giving rise to more reliable functioning. Important papers on this subject are references 3, 4 and 5. Especially von Neumann's paper in "Automata Studies" has been a challenge for our investigation.

MALFUNCTION OF FORMAL NEURONS

Considering a formal neuron we can distinguish four sites of possible erroneous activity. We will proceed to consider these and end up with two kinds which can be functionally expressed by two probabilities of error.

The connection of an input line to a formal neuron can fail to transfer the state of the input line to the formal neuron. We will call this synaptic error. To be quite clear we postulate a probability Ps of synaptic error which consists in the formal neuron receiving excitation +1 (-1) from an input line which is 'off' and has a positive (negative) connection, and the formal neuron receiving no excitation from an input line which is 'on.' Furthermore this probability Ps is assumed to be equal for all input lines and independent of all activity going on.

A second site of erroneous action is the output line and consists in a failure of the output line to be in the state prescribed by the activity of the formal neuron. We assume that the effect of this axonal error can be represented functionally by an independent probability Pa which is equal for all formal neurons.

It is clear that synaptic error and axonal error are both of the all-ornone type and can be combined, for each line between formal neurons within a neuronal network, to one error probability composed of the two error probabilities at each end of the line. Note that unreliable circuitry or interconnections can be regarded as incorporated in the above described type of

error.

A third possibility of malfunction of formal neurons is due to fluctuations in the strength of the signals it receives from the input lines. These fluctuations are of minor importance in biological neurons as well as in hardware realizations of formal neurons. Furthermore its effect tends to diminish as the number of input lines increases and it will not be considered directly. Note that it is possible to comprise the effect of signal strength fluctuations in that of fluctuations of threshold.

The fourth phenomenon that affects the reliability of a formal neuron is the fluctuation of the threshold about its nominal value. This has continuous character and its effect with increasing number of input lines is very important (cf next section). The assumptions we will make on the nature of threshold fluctuations are in accordance with measurements and discussions reported in papers by Pecher (ref. 6), Rosenblith (ref. 7), Frishkopf (ref. 8), and Viernstein and Grossman (ref. 9).

In defining the synaptic and axonal error probabilities as we did, we are not completely sustained by neurophysiological data. Evidence relevant to our investigation is rather scarce. On the other hand our assumptions are not inconsistent with the available evidence.

EFFECTS OF MALFUNCTION OF FORMAL NEURONS

Neglecting signal strength fluctuations the algebraic sum of the excitations by the signals from the input lines is always of integral value. This insures that the most favorable setting of a threshold is exactly half way between two integers and a fluctuation of the threshold less than 0.5 has no effect. We assume the distribution of the threshold t to be Gaussian about the mean . Important for the further discussion is the dependence of the equivalent probability of error pt of a formal neuron, due to threshold fluctuation, on the number of input lines n. For a certain class of polyphecks the dependence of pt on n is calculated. These polyphecks have negative connection from all n input lines and a threshold

0 = -(n+1)/2 for n even, and 0 = -(n+2)/2 for n odd.

The assumptions made to calculate the dependence of pt on n are that all input configurations of activity of the input lines are equiprobable and that the standard deviation σ of the Gaussian distribution of the threshold is independent of n. This last means that we assume that the mechanism of the threshold fluctuations is independent of the input to the formal neuron. In figure 2 the results are shown and these indicate that pt decreases with increasing n.

Remark that with input configurations which are not equiprobable the value of Pt is always lower than those shown in the curves of figure 2.

Another remark of importance is that for majority of organs, that is for formal neurons with positive connections from all input lines, the same decrease of Pt with increasing n is obtained.

We can simplify the subsequent discussion by taking the probability of error due to threshold fluctuations as fixed independent of n, i.e., pt is an upper bound to the error due to threshold fluctuations.