<p>A nice reference is "Part C" of <a href="http://rads.stackoverflow.com/amzn/click/0444863885" rel="noreferrer">Handbook of Mathematical Logic</a> edited by Barwise. Part C includes the following chapters:</p>

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

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

CC BY-SA 2.5
2010-11-28T11:29:51.960Z
2010-11-29T13:35:09.787Z
2010-11-29T13:35:09.787Z
Dai Le
<p>Most logic/complexity theory books have a chapter on computability.</p>
<h3>Textbook:</h3>
<p>Dexter Kozen, &quot;<a href="http://books.google.ca/books?id=AolrsLBq3u0C" rel="nofollow noreferrer">Theory of Computation</a>&quot;, Springer, 2006</p>
<p>Douglas S. Bridges, &quot;<a href="http://books.google.ca/books?id=ii5kKQJWDzEC" rel="nofollow noreferrer">Computability: a Mathematical Sketchbook</a>&quot;, Springer, 1994</p>
<p>Nigel Cutland, &quot;<a href="http://books.google.ca/books?id=wAstOUE36kcC" rel="nofollow noreferrer">Computability, an Introduction to Recursive Function Theory</a>&quot;, Cambridge University Press, 1980</p>
<p>Barry S. Cooper, &quot;<a href="http://books.google.ca/books?id=SJvt8ELnMakC" rel="nofollow noreferrer">Computability Theory</a>&quot;, Chapman &amp; Hall/CRC, 2004</p>
<h3>More advanced book:</h3>
<p>Robert I. Soare, &quot;<a href="http://books.google.ca/books?id=9I7Pl00LU5gC" rel="nofollow noreferrer">Recursively Enumerable Sets and Degrees</a>&quot;, Springer-Verlag, 1987</p>
<p>Robert I. Soare, &quot;Computability Theory and Applications: The Art of Classical Computability&quot;</p>
<p>Piergiorgio Odifreddi, &quot;<a href="http://books.google.ca/books?id=ahBLqshTFMwC" rel="nofollow noreferrer">Classical Recursion Theory</a>&quot;, vol I (1989) &amp; II (1999)</p>
<p>Edward R. Griffor, &quot;<a href="http://books.google.ca/books?id=KqeXZ4pPd5QC" rel="nofollow noreferrer">Handbook of Computability Theory</a>&quot;, Elsevier, 1999</p>

CC BY-SA 2.5
2010-11-29T09:36:00.623Z
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").
Sadeq Dousti
CC BY-SA 2.5
2010-11-29T10:24:18.347Z
@Sadeq Dousti: You are right, I think I have copied the title from author's webpage.
Kaveh
CC BY-SA 2.5
2010-11-29T15:27:18.620Z
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?
Sadeq Dousti
CC BY-SA 2.5
2010-11-29T17:51:15.327Z
@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.
Kaveh
CC BY-SA 2.5
2010-11-28T16:11:32.153Z
2010-11-29T15:26:19.167Z
2020-06-17T09:38:08.363Z
Kaveh
<p>I like the syllabus Sebastiaan Terwijn wrote back in 2004 (accessible at <a href="http://www.math.ru.nl/~terwijn/teaching.html">http://www.math.ru.nl/~terwijn/teaching.html</a>).  It covers recursive functions and sets, r.e. sets, the arithmetical hierarchy, Turing degrees, the priority method, and a few applications, including incompleteness theorems.</p>

CC BY-SA 2.5
2010-11-28T14:25:36.663Z
2010-11-28T14:25:36.663Z
Michaël Cadilhac
<p>I found these books at my disposal. I cross-checked not to include those books <a href="https://cstheory.stackexchange.com/questions/3373/3380#3380">cited by Kaveh</a>, but my eyes might have made a mistake.</p>

<ul>
<li><a href="http://rads.stackoverflow.com/amzn/click/0824700260" rel="nofollow noreferrer">Complexity, Logic, and Recursion Theory</a></li>
<li><a href="http://rads.stackoverflow.com/amzn/click/0521557364" rel="nofollow noreferrer">Computability, Enumerability, Unsolvability; Directions in Recursion Theory</a></li>
<li><a href="http://rads.stackoverflow.com/amzn/click/0262680521" rel="nofollow noreferrer">Theory of Recursive Functions and Effective Computability</a></li>
<li><a href="http://rads.stackoverflow.com/amzn/click/019508232X" rel="nofollow noreferrer">Recursion Theory for Metamathematics</a></li>
</ul>

CC BY-SA 2.5
2010-11-29T09:33:22.297Z
@Kaveh: Thanks. It seems that I'm in need of a pair of glasses :)
Sadeq Dousti
CC BY-SA 2.5
2010-11-28T20:09:45.740Z
2010-11-29T09:33:45.883Z
2017-04-13T12:32:28.743Z
Sadeq Dousti
<p>Could you recommend a survey article or textbook chapter that introduces the theory of recursive functions? Thanks</p>

<reference-request><computability>
Survey Article on the Theory of Recursive Functions?
ShyPerson
# Survey Article on the Theory of Recursive Functions?

(Asked by: username_0 on 2010-11-28)

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

**Tags:** reference-request, computability


---

## 4 answers

### Answer by username_1 on 2010-11-28. Score: 10

A nice reference is "Part C" of [Handbook of Mathematical Logic](http://rads.stackoverflow.com/amzn/click/0444863885) 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.


---

### Answer by username_2 on 2010-11-28. Score: 9

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

### Textbook:

Dexter Kozen, "[Theory of Computation](http://books.google.ca/books?id=AolrsLBq3u0C)", Springer, 2006

Douglas S. Bridges, "[Computability: a Mathematical Sketchbook](http://books.google.ca/books?id=ii5kKQJWDzEC)", Springer, 1994

Nigel Cutland, "[Computability, an Introduction to Recursive Function Theory](http://books.google.ca/books?id=wAstOUE36kcC)", Cambridge University Press, 1980

Barry S. Cooper, "[Computability Theory](http://books.google.ca/books?id=SJvt8ELnMakC)", Chapman & Hall/CRC, 2004

### More advanced book:

Robert I. Soare, "[Recursively Enumerable Sets and Degrees](http://books.google.ca/books?id=9I7Pl00LU5gC)", Springer-Verlag, 1987

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

Piergiorgio Odifreddi, "[Classical Recursion Theory](http://books.google.ca/books?id=ahBLqshTFMwC)", vol I (1989) & II (1999)

Edward R. Griffor, "[Handbook of Computability Theory](http://books.google.ca/books?id=KqeXZ4pPd5QC)", Elsevier, 1999

> **Comments:**
> **username_3**: 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").  
> **username_2**: @username_3: You are right, I think I have copied the title from author's webpage.  
> **username_3**: 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?  
> **username_2**: @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.  

---

### Answer by username_4 on 2010-11-28. Score: 6

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.


---

### Answer by username_3 on 2010-11-28. Score: 5

I found these books at my disposal. I cross-checked not to include those books [cited by username_2](https://cstheory.stackexchange.com/questions/3373/3380#3380), but my eyes might have made a mistake.

* [Complexity, Logic, and Recursion Theory](http://rads.stackoverflow.com/amzn/click/0824700260)
* [Computability, Enumerability, Unsolvability; Directions in Recursion Theory](http://rads.stackoverflow.com/amzn/click/0521557364)
* [Theory of Recursive Functions and Effective Computability](http://rads.stackoverflow.com/amzn/click/0262680521)
* [Recursion Theory for Metamathematics](http://rads.stackoverflow.com/amzn/click/019508232X)

> **Comments:**
> **username_3**: @username_2: Thanks. It seems that I'm in need of a pair of glasses :)  

---

