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?

*solution*of a net as a set of logical sentences of the form ``neuron 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 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 is firing at time if and
only if none of the neurons having an inhibitory
synapse towards it was firing at time
and more than neurons having an excitatory
synapse towards it were firing at time
. The positive integer is called the *excitation
threshold* of neuron .

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