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