Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets
..."The book, written by one of the main researchers on the field, gives a complete account of the theory of r.e. degrees. .... The definitions, results and proofs are always clearly motivated and explained before the formal presentation; the proofs are described with remarkable clarity and conciseness. The book is highly recommended to everyone interested in logic. It also provides a useful background to computer scientists, in particular to theoretical computer scientists." Acta Scientiarum Mathematicarum, Ungarn 1988 ..."The main purpose of this book is to introduce the reader to the main results and to the intricacies of the current theory for the recurseively enumerable sets and degrees. The author has managed to give a coherent exposition of a rather complex and messy area of logic, and with this book degree-theory is far more accessible to students and logicians in other fields than it used to be." Zentralblatt für Mathematik, 623.1988
What people are saying - Write a review
Other editions - View all
Recursively Enumerable Sets and Degrees: A Study of Computable Functions and ...
Robert Irving Soare
No preview available - 1987
A-recursive arithmetical hierarchy As+i assume atomless automorphism basic module Boolean algebra Chapter characteristic function choose the least coinfinite r.e. set computation Corollary define the recursive Definition deg(A denote disjoint e-state elements end of stage Exercise exists an r.e. finite sets function f Hence hh-simple high r.e. Hint hypersimple hypothesis index sets induction infinite injury Jockusch Lachlan lattice Lemma liminf lims low r.e. marker maximal sets minimal pair node nonrecursive r.e. set Note otherwise p.r. function partial function partial recursive function Post's Post's problem primitive recursive proof of Theorem Prove r-maximal r.e. degrees Recursion Theorem recursive enumeration recursive sets relativized restraint function s-m-n Theorem Sacks satisfied Soare Splitting Theorem Step strategy subset superset Theorem 3.1 tree Turing Turing degrees Vn n€w We,s Yates
Page x - The conclusion is unescapable that even for such a fixed, well defined body of mathematical propositions, mathematical thinking is, and must remain, essentially creative. To the writer's mind, this conclusion must inevitably result in at least a partial reversal of the entire axiomatic trend of the late nineteenth and early twentieth centuries, with a return to meaning and truth as being of the essence of mathematics.
Page vii - Plans for books are discussed and argued about at length. Later, encouragement is given and revisions suggested. But it is the authors who do the work; if. as we hope, the series proves of value, the credit will be theirs. History of the fi-Group. During 1968 the idea of an integrated series of monographs on mathematical logic was first mooted. Various discussions led to a meeting at Oberwolfach in the spring of 1969. Here the founding members of the group (R.
Page viii - Bibliography, in an outstandingly generous way. We could always rely on their readiness to provide help wherever it was needed. Assistance in many various respects was provided by Drs. U. Feigner and K. Gloede (till 1975) and Drs. D. Schmidt and H. Zeitler (till 1979). Last but not least, our indefatigable secretary Elfriede Ihrig was and is essential in running our enterprise. We thank all those concerned. Heidelberg, September 1982 R.
Page vii - Logik" of the Heidelberger Akademie der Wissenschaften) On Perspectives. Mathematical logic arose from a concern with the nature and the limits of rational or mathematical thought, and from a desire to systematize the modes of its expression. The pioneering investigations were diverse and largely autonomous. As time passed, and more particularly in the last two decades, interconnections between different lines of research and links with other branches of mathematics proliferated. The subject is now...
All Book Search results »
Complexity Theory and Cryptology: An Introduction to Cryptocomplexity
No preview available - 2005