9
$\begingroup$

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

Improve this question
$\endgroup$

4 Answers 4

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
9
$\begingroup$

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

Textbook:

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

Improve this answer
$\endgroup$
4
  • $\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$
    – Sadeq Dousti
    Commented Nov 29, 2010 at 9:36
  • $\begingroup$ @Sadeq Dousti: You are right, I think I have copied the title from author's webpage. $\endgroup$
    – Kaveh
    Commented Nov 29, 2010 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$
    – Sadeq Dousti
    Commented Nov 29, 2010 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
    Commented Nov 29, 2010 at 17:51
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @Kaveh: Thanks. It seems that I'm in need of a pair of glasses :) $\endgroup$
    – Sadeq Dousti
    Commented Nov 29, 2010 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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