At the moment, I’m going to Thomas Forster’s Part III maths course on computable functions. I’ve put together an introductory reading list on the elementary stuff in the opening lectures, which may be of use/interest to others.
As usual, comments/corrections/suggested additions are always welcome — especially perhaps, in this case, pointers to particularly good online lecture notes, etc.
7 thoughts on “Reading list on computable functions”
We used Computability, Complexity, and Languages by Davis, Sigal and Weyuker in my undergraduate “computability theory” course. I found it clear but terse. Perhaps too much for an “introductory” reading list? I confess that it seems I find them all difficult, although I can nevertheless learn from them all too.
As another good introduction, I would also add Douglas Bridges’ “Computability – A mathematical sketchbook”. It’s comparable to Cutland’s book; more compact and terse, but still very well written and it uses TM’s instead of URM’s, which may facilitate the transition for someone who wishes to proceed to Complexity Theory, for example.
I would be interested in any opinions on:
Raymond Smullyan, Recursion Theory for Metamathematics (Oxford Logic Guides)
Nicholas Pippenger, Theories of Computability
I don’t know the Pippenger book at all (though looking at the table of contents, it does seem to be coming at things with a rather different focus). Smullyan’s book, like all his books, has terrific virtues; but again its coverage seems slightly skew to the mainstream you want mathmos new to the area to know.
A new edition of Cooper is about to appear, if anyone is considering buying a copy.
Amazon.co.uk says 26 July 2011.
I have not checked the new book by the late Herbert Enderton (anyone has checked it?), but it seems worth considering his inclusion in this bibliography list.
I mean the book “Computability Theory: An Introduction to Recursion Theory” http://www.amazon.com/Computability-Theory-Introduction-Recursion/dp/0123849586
Thanks for that. Yes, I knew that Enderton’s book is now out, and I’d expect it to be good; but I haven’t seen it yet so don’t want to recommend it sight-unseen. (And it isn’t available so far in the university library system here, which I guess is another reason not to mention it in in the current version of the reading list.)