Functional programming is on everyone’s lips and concepts from functional programming are being adopted everywhere in imperative languages. At the moment I am also taking a closer look at these concepts and would like to publish my findings here in the form of a series of articles. But let’s start with a short historical review.

I have to admit that the more I researched the story, the more fascinating I found it.

It began in 1936, when Alonzo Church’s April publication “An unsolvable Problem of Elementary Number Theory” suggested that the decision problem was unsolvable.

…the Entscheidungsproblem is unsolvable in the case of any system of symbolic logic which is ω-consistent (ω-widerspruchsfrei) in the sense of Gödel (loc. cit., p. 187) and is strong enough to allow certain comparatively simple methods of definition and proof.

– Alonzo Church, An unsolvable Problem of Elementary Number Theory

To reach this conclusion, he defined the Lambda calculus, which laid the foundation for functional programming.

At about the same time, Alan Turing also dealt with the decision problem and published “On computable numbers, with an application to the Entscheidungsproblem” in August 1936. In it he had to refer to Church’s work, which probably displeased him somewhat (see Alan Turing — a short biography).

In a recent paper Alonzo Church has introduced an idea of “effective calculability”, which is equivalent to my “computability”, but is very differently defined. Church also reaches similar conclusions about the Entscheidungsproblem.

– Alan Turing, On computable numbers, with an application to the Entscheidungsproblem

Part of Alan Turing’s paper was the definition of automatic machines or a-machines, which are better known today as Turing machines and laid the foundation for imperative programming. In the appendix of said paper Turing also states that the classes “effective calculability” (lambda calculus) and “computability” (Turing machine) are equally powerful.

Turing came to Princeton University in September 1936 and began his PhD under Church. I also find it remarkable that other well-known personalities in computer science received their PhDs under Church, such as Kleene, Scott, Kemeny

As you can see from these excerpts from history, the respective basic concepts of both programming paradigms (functional and imperative) emerged, interestingly enough, in 1936, but independently of each other as proof that the decision problem is unsolvable.