Alonzo Church (left) and Alan Turing (right)
Alan Turing is no doubt the most well-known of all computer scientists. His Turing machine is justly famous, and the video below shows a really cool Lego version of it.
However, it is not widely known that the fundamental result in Turing’s 1936 paper (“On Computable Numbers, with an Application to the Entscheidungsproblem” – with errors later corrected in 1937: i, ii, iii) was not actually new. This is revealed on the second page of Turing’s paper, where Turing admits “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 ‡. The proof of equivalence between ‘computability’ and ‘effective calculability’ is outlined in an appendix to the present paper.”
It seems that Max Newman encouraged Turing to explain how his work related to the result that Alonzo Church had already obtained, lobbied the Secretary of the London Mathematical Society to still permit publication of Turing’s paper, and arranged for Turing to go to Princeton, where Church would be his PhD supervisor (Church also supervised 34 other students). It’s a terrible feeling for a student to be “gazumped” like that, and invaluable to have helpful people backing you up. Turing went on to have a colourful, but relatively short, life. Church lived to 92, but was staid in comparison.
Church’s notation, the lambda calculus, has been quite influential, spawning programming languages such as Lisp and Haskell, as well as more theoretical work. The fundamental feature of lambda calculus, the anonymous function written function (x) { e }, has been incorporated into many other programming languages as well. Consider the following code in R, for example:
i <- function (x) { x }
k <- function (x) { function (y) { x } }
s <- function (x) { function (y) { function (z) { x(z)(y(z)) } } }
y <- function (f) { (function (x) { f(x(x)) }) (function (x) { f(x(x)) }) }Notice that functions can themselves be arguments to other functions, and in x(x), a function is applied to itself.
The object i is the identity function, so that i(3) reduces to 3. The expressions k(3)(4) and s(k)(k)(3) also reduce to 3. The object y is the Y combinator, with y(k(3)) reducing to 3, and y(i) generating infinite recursion. The following code uses y to generate the factorial function:
fact <- y (function (g) { function (x) { if (x == 0) 1 else x * g (x - 1) } })
fact (3)The appendix that Turing was forced to write was perhaps the most significant aspect of his 1936 paper. Showing that his definition of computability was equivalent to that of Church led to the Church–Turing thesis – the idea that that is the only kind of computability (at least on numbers). Independently of Turing, Emil Post produced another equivalent form of computability in 1936. Yet another form came out of Russia. Even Conway’s Game of Life (below) turns out to capture the same kind of computability, though in an inherently parallel form:
See more on the Church–Turing thesis at plato.stanford.edu. There was also a series of interesting talks presented on Church and Turing in 2012, including this one by Philip Wadler:
While the lambda calculus was probably the version of computability with the largest impact on programming languages, the more practical Von Neumann architecture probably had the largest impact on hardware design. It is difficult to imagine what the world would look like without those two concepts.
Scientific Gems 