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.

This entry was posted in Logic. Bookmark the permalink.

7 Responses to Reading list on computable functions

  1. boumol says:

    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”

    • Peter Smith says:

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

  2. Rowsety Moid says:

    A new edition of Cooper is about to appear, if anyone is considering buying a copy. says 26 July 2011.

  3. Rowsety Moid says:

    I would be interested in any opinions on:

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

    Nicholas Pippenger, Theories of Computability

    • Peter Smith says:

      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.

  4. Joao Soares says:

    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.


  5. Joe says:

    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.

Leave a Reply

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