[FOM] History of computable functions
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.
More information about the FOM