Reading list on computable functions

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”

  1. 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.

  2. 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.


  3. I would be interested in any opinions on:

    Raymond Smullyan, Recursion Theory for Metamathematics (Oxford Logic Guides)

    Nicholas Pippenger, Theories of Computability

    1. 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.

    1. 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.)

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top