How mathematicians influenced programming

Notes.

This is a brief account of how developments in abstract mathematics in the early to mid 20th century (kind of accidentally) influnced all the programming languages.

It all starts with a couple of mathematicians — like Alonzo Church, Haskell Curry, Schönfinkel. These guys founded the λ-calculus and related theory of combinatory logic with two goals in mind:

(1) Developing a general theory of functions
(2) Making this theory the foundation of logic and some parts of math

Church developed the general function theory but was unable to prove it to be the foundation of logic and mathematics. The Kleene-Rosser paradox discouraged him. On the other hand, Curry did try address the paradoxes but his theory has been termed as “too weak” to support logic. Both Church and Curry did develop a strong system of functions, though.

After having failed at goal number two, Church retained focus on goal number one and came up with the concept of λ-definability or “effective computability”. Kleene — who was Church’s student and Church himself, independently, later established a connection between λ-definability and Gödel-Herbrand’s general recursive functions. Kleene formulated the recursive function theory.

Ultimately, another student of Church, Alan Turing, came up with the notion of “Turing completeness” and proved that λ-calculus (along with the recursive function theory) is Turing complete. This meant you could solve any “solvable” problem using the notation of λ-calculus and recursive functions.

λ-calculus then became a paradigmatic programming language and directly influenced many of the early programming languages — Algol, Pascal, Lisp.

We, the programmers of today, are oblivious to how mathematics had a deep impact on the languages that we use today. There are so many layers, so much abstraction everywhere that I sometimes wonder if even lanuage designers are aware of how their thoughts are indirectly influenced by the lives of the mathematicians listed in this blog.

P.S: I have not included any hyperlinks here. I wanted to quickly note this down. The interested reader is requested to Google-search whatever interests her.

Thank you!