Could you recommend a survey article or textbook chapter that introduces the theory of recursive functions? Thanks


A nice reference is "Part C" of Handbook of Mathematical Logic edited by Barwise. Part C includes the following chapters:

  • Herbert B. Enderton, Elements of recursion theory
  • Martin Davis, Unsolvable problems
  • Michael O. Rabin, Decidable theories
  • Stephen G. Simpson, Degress of unsolvability: a survey of results
  • Richard A. Shore, $\alpha$-recursion theory
  • Alexander Kechris and Yiannis N. Moschovakis, Recursion in higher types
  • Peter Aczel, An introduction to inductive definitions
  • Donald A. Martin, Descriptive set theory

The chapters are of very high quality and written by leading logicians. This handbook will take you quite far into the world of mathematical logic.


Most logic/complexity theory books have a chapter on computability.


Dexter Kozen, "Theory of Computation", Springer, 2006

Douglas S. Bridges, "Computability: a Mathematical Sketchbook", Springer, 1994

Nigel Cutland, "Computability, an Introduction to Recursive Function Theory", Cambridge University Press, 1980

Barry S. Cooper, "Computability Theory", Chapman & Hall/CRC, 2004

More advanced book:

Robert I. Soare, "Recursively Enumerable Sets and Degrees", Springer-Verlag, 1987

Robert I. Soare, "Computability Theory and Applications: The Art of Classical Computability"

Piergiorgio Odifreddi, "Classical Recursion Theory", vol I (1989) & II (1999)

Edward R. Griffor, "Handbook of Computability Theory", Elsevier, 1999

  • $\begingroup$ In the list of textbooks, the first one "Computably Enumerable Sets and Degrees" has a different title form what you linked ("Recursively enumerable sets and degrees"). $\endgroup$ – M.S. Dousti Nov 29 '10 at 9:36
  • $\begingroup$ @Sadeq Dousti: You are right, I think I have copied the title from author's webpage. $\endgroup$ – Kaveh Nov 29 '10 at 10:24
  • $\begingroup$ So, I edited it to reflect the title as published. PS: The book "Computability Theory and Applications: The Art of Classical Computability" is yet to be published, right? $\endgroup$ – M.S. Dousti Nov 29 '10 at 15:27
  • $\begingroup$ @Sadeq: I think he prefers to avoid using the word recursive for computable recently. ps: I think so, but you can probably ask him to get the draft version, we have used it in a course a few years ago. $\endgroup$ – Kaveh Nov 29 '10 at 17:51

I like the syllabus Sebastiaan Terwijn wrote back in 2004 (accessible at http://www.math.ru.nl/~terwijn/teaching.html). It covers recursive functions and sets, r.e. sets, the arithmetical hierarchy, Turing degrees, the priority method, and a few applications, including incompleteness theorems.


I found these books at my disposal. I cross-checked not to include those books cited by Kaveh, but my eyes might have made a mistake.

  • $\begingroup$ @Kaveh: Thanks. It seems that I'm in need of a pair of glasses :) $\endgroup$ – M.S. Dousti Nov 29 '10 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.