Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets

by Robert I. Soare

The first part consists of an introduction to the theory of computation and recursive function theory, including definitions of computable functions, Turing machines, partial recursive functions, recursively enumerable sets, the Kleene recursion theorem etc. The second part is a comprehensive study of recursively enumerable sets and their degrees.

Genres: Mathematics, Logic

437 pages, Hardcover

First published January 1, 1987

Reviews

[Peter Gerdes · Rating 5 out of 5]

This is THE book to learn real recursion theory from. It isn't as good a reference as Odefreddi (though soare has more on the r.e. degrees) but it actually explains what is happening and offers insight into the subject.

This isn't a book for the non-mathematician who just wants to know what all this stuff about Turing machines is about. This is a full course that takes one from the beginnings of the subject to a point where you are ready to read (and produce) recent papers. I personally wish it had a little bit more on forcing constructions and other non-re constructions (this part is frustratingly short) but the book is more coherent and reasonably sized for their omission.

The approach taken is more modern than that of Rogers and much preferable. Obscure rarely used notions (e.g., the Medvedev lattice) and repetition of the same material in different contexts is avoided in favor of going through more complex constructions and results in the r.e.-degrees.

[liza · Rating 5 out of 5]

god is logic, else why may we reason?