COSC 4111 AF - Additional References

  • N.J. Cutland, Computability An introduction to recursive function theory, Cambridge University Press, 1980. (This book has a fairly similar approach to that of Cook's notes.)
  • J. Martin, McGraw-Hill, 2003. (There is a good treatment of recursive function theory in Chapter 12, and most topics of the course are covered in Chapters 9-14, but the author uses Turing machines and there is no coverage of register machines and some advanced topics of the course, like the recursion theorem.)
  • Hopcroft, J.E. and Ullman, J.D., Introduction to Automata, Languages and Programming, Addison Wesley, 1979.
  • Lewis, H.R. and Papadimitriou, C.H., Elements of the Theory of Computation (Second Edition), Prentice Hall, 1998.
  • Garey,M.R. and Johnson, D.S., Computers and Intractibility, A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979.