[FOM] History of computable functions

William Tait williamtait at mac.com
Wed Nov 4 15:30:35 EST 2009

On Nov 4, 2009, at 2:12 AM, Andrej Bauer wrote:

> A student of mine is working on a seminar in which he will show in
> excruciating detail that the general recursive functions embed in
> untyped lambda calculus (this is at undergraduate level). He would
> like to know more about the history of computable functions, lambda
> calculus, Turing machines, etc., with a reasonably correct timeline of
> who did what when. Can someone please suggest some reading material?

On lambda calculus and combinators, I would recommend

F Cardone, J R Hindley, The history of lambda and combinators, in  
Handbook of the History of Logic, Volume 5, D M Gabbay and J Woods  
(eds) (Amsterdam: Elsevier Co., to appear).

It can be downloaded from Hindley's website


There is a lot of historical material on computable functions in P.G.  
Odifreddi's two-volume work, Classical Recursion Theory; but I haven't  
really read much of it.

Looking through the papers in Martin Davis's _The Undecidable_ would  
certainly give some historical perspective.

Bill Tait

More information about the FOM mailing list