Posts Tagged ‘Turing machine’

Church, Alonzo and the Lambda Calculus

December 16, 2009

Today’s topic: Alonzo Church.

Church created the Lambda Calculus, which set the ground for functional programming and LISP.

He also supervised Alan Turing, and together they proved the equivalence of the Lambda Calculus and Turing Machine for computing the values of mathematical functions.

He’s one of the grandparents of computer science but he doesn’t seem to get a lot of attention these days.

Princeton in the 1930’s was an exciting place for logic. There was Church together with his students Rosser and Kleene. There was John von Neumann. Alan Turing, who had been thinking about the notion of effective calculability, came as a visiting graduate student in 1936 and stayed to complete his Ph.D. under Church. And Kurt Gödel visited the Institute for Advanced Study in 1933 and 1935, before moving there permanently.


An introduction to the Lambda Calculus:

An interesting rant about how Church’s and Turing’s theories have been twisted in literature over the past few decades:

The Lambda Calculus is especially intriguing to computer scientists because substitution discourages side-effects.  Minimizing the side-effects caused by the functions & methods we write is a good way of minimizing bugs, and also makes unit testing a whole lot easier for all you Test Driven Development nuts.

Reading about Church and his Lambda Calculus can give a developer a whole new perspective on her approach to programming.

Happy reading!