next up previous contents index
Next: What functions can a Up: Finite-state machines and neural Previous: Finite-state machines and neural   Contents   Index


McCulloch and Pitts' neural logical calculus

The paper by McCulloch and Pitts (1943) is commonly regarded as the inception of two fields of research. One is the theory of finite-state machines as a model of computation. The other one is the field of artificial neural networks. This is an important and widely cited paper, yet a difficult one to understand. the notation used by McCulloch and Pitts (1943) is hard to follow for us nowadays, but it also was for Kleene (1956), who expresses this very clearly:

The present article is partly an exposition of their results; but we found the part of their [McCulloch and Pitts'] paper dealing with arbitrary nerve nets obscure, so we have proceeded independently there.
Later on, having found an apparent flaw in one of the results by McCulloch and Pitts (1943), Kleene (1956) says:
This apparent counterexample discouraged us from further attempts to decipher part III of McCulloch-Pitts [1943].

The paper by McCulloch and Pitts (1943) paper is properly titled ``A logical calculus of the ideas immanent in nervous activity'': after stating a careful and well argumented selection of simplifications of the behavior of real neurons, they develop a logical apparatus to define:

The main result is that any TPE is realizable by a non-recurrent neural net, that is, there is always a net, whose synapses or connections do not form cycles, which can compute any given TPE (McCulloch and Pitts (1943) call non-recurrent nets ``nets without circles''). This result follows from the fact that the neurons in McCulloch and Pitts (1943) are described by a TPE (their eq. (1)) which basically states that a neuron $i$ is firing at time $t$ if and only if none of the neurons having an inhibitory synapse towards it was firing at time $t-1$ and more than $\theta_i$ neurons having an excitatory synapse towards it were firing at time $t-1$. The positive integer $\theta_i$ is called the excitation threshold of neuron $i$.

To understand the computational behavior of nets with circles, one can follow Kleene (1956)3.1. His notation is closer to the one used nowadays, and the results are more general. Kleene (1956) characterized with mathematical expressions the set of all input neuron activation sequences that bring a given net with circles to a particular state after they have been completely processed, and discovered interesting regularities among them. Kleene (1956) called them ``regular events''; we currently call them ``regular expressions'' in language theory (Hopcroft and Ullman, 1979, 28).


next up previous contents index
Next: What functions can a Up: Finite-state machines and neural Previous: Finite-state machines and neural   Contents   Index
Debian User 2002-01-21