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 concepts of solution of a net and realizability of a logical predicate by a net. After dividing the neurons in one net in two groups, that is, input neurons (``peripheral afferents'') that do not get signals from any other neuron in the net, and the rest of neurons, they go on to define a method to answer the following two questions in the most general way possible:
  • What does a given net compute?
  • Can a given net compute a given logical sentence?
  Neurons are in two possible states: firing and not firing, and thus, they define for each neuron $i$ a predicate that is true when the neuron is firing at a given time $t$: $N_i(t)$. They define the solution of a net as a set of logical sentences of the form ``neuron $i$ is firing if and only if'' a given logical combination of the firing predicates of input neurons at previous times and some constant sentences including firing predicates of these same neurons at $t=0$ is true. These sentences are a solution for a net if they are all true for it. In other words, the sentences describe what the net computes. Conversely, such an ``if and only if'' sentence is called realizable by a net if it is true for that net; that is, when the net can compute it.

• A class of logical expressions (including predicates which have predicates as functions) which they call temporal propositional expressions (TPE). These predicates have a single free variable (which will be identified as discrete time), and are recursively defined such that (a) any predicate of one argument is a TPE; (b) the logical conjunction (and), disjunction (or) and negated conjunction (and not) of any two TPEs with the same variable is a TPE; (c) a TPE in which the value of the time variable is substituted by its predecessor (time delay) is a TPE; and nothing else is a TPE.

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).