Volume II of Classical Recursion Theory describes the universe from a local (bottom-up or synthetical) point of view, and covers the whole spectrum, from the recursive to the arithmetical sets. The first half of the book provides a detailed picture of the computable sets from the perspective of Theoretical Computer Science. Besides giving a detailed description of the theories of abstract Complexity Theory and of Inductive Inference, it contributes a uniform picture of the most basic complexity classes, ranging from small (...) time and space bounds to the elementary functions, with a particular attention to polynomial time and space computability. It also deals with primitive recursive functions and larger classes, which are of interest to the proof theorist. The second half of the book starts with the classical theory of recursively enumerable sets and degrees, which constitutes the core of Recursion or Computability Theory. Unlike other texts, usually confined to the Turing degrees, the book covers a variety of other strong reducibilities, studying both their individual structures and their mutual relationships. The last chapters extend the theory to limit sets and arithmetical sets. The volume ends with the first textbook treatment of the enumeration degrees, which admit a number of applications from algebra to the Lambda Calculus. The book is a valuable source of information for anyone interested in Complexity and Computability Theory. The student will appreciate the detailed but informal account of a wide variety of basic topics, while the specialist will find a wealth of material sketched in exercises and asides. A massive bibliography of more than a thousand titles completes the treatment on the historical side. (shrink)

It is shown that if A and C are sets of degrees uniformly recursive in 0' with $\mathbf{0} \nonin \mathscr{C}$ then there is a degree b with b' = 0', b ∪ c = 0' for every c ∈ C, and $\mathbf{a} \nleq \mathbf{b}$ for every a ∈ A ∼ {0}. The proof is given as an oracle construction recursive in 0'. It follows that any nonrecursive degree below 0' can be joined to 0' by a degree strictly below 0'. (...) Also, if $\mathbf{a ' and a" = 0" then there is a degree b such that a ∪ b = 0' and a ∩ b = 0. (shrink)

It is shown that many different problems have the same degree of unsolvability. Among these problems are: THE INDUCTIVE INFERENCE PROBLEM. Infer in the limit an index for a recursive function f presented as f(0), f(1), f(2),.... THE RECURSIVE INDEX PROBLEM. Decide in the limit if i is the index of a total recursive function. THE ZERO NONVARIANT PROBLEM. Decide in the limit if a recursive function f presented as f(0), f(1), f(2),... has value unequal to zero for infinitely many (...) arguments. Finally, it is shown that these unsolvable problems are strictly easier than the halting problem. (shrink)

Inductive inference considers two types of queries: Queries to a teacher about the function to be learned and queries to a non-recursive oracle. This paper combines these two types — it considers three basic models of queries to a teacher (QEX[Succ], QEX[ The results for each of these three models of query-inference are the same: If an oracle is omniscient for query-inference then it is already omniscient for EX. There is an oracle of trivial EX-degree, which allows nontrivial query-inference. Furthermore, (...) queries to a teacher cannot overcome differences between oracles and the query-inference degrees are a proper refinement of the EX-degrees. In the case of finite learning, the query-inference degrees coincide with the Turing degrees. Furthermore oracles can not close the gap between the different types of queries to a teacher. (shrink)

Most theories of learning consider inferring a function f from either observations about f or, questions about f. We consider a scenario whereby the learner observes f and asks queries to some set A. If I is a notion of learning then I[A] is the set of concept classes I-learnable by an inductive inference machine with oracle A. A and B are I-equivalent if I[A] = I[B]. The equivalence classes induced are the degrees of inferability. We prove several results about (...) when these degrees are trivial, and when the degrees are omniscient. (shrink)

We prove that the set of all recursive functions cannot be inferred using first-order queries in the query language containing extra symbols $\lbrack +, . The proof of this theorem involves a new decidability result about Presburger arithmetic which is of independent interest. Using our machinery, we show that the set of all primitive recursive functions cannot be inferred with a bounded number of mind changes, again using queries in $\lbrack +, . Additionally, we resolve an open question in [7] (...) about passive versus active learning. (shrink)

We prove that the set of all recursive functions cannot be inferred using first-order queries in the query language containing extra symbols $\lbrack +, < \rbrack$. The proof of this theorem involves a new decidability result about Presburger arithmetic which is of independent interest. Using our machinery, we show that the set of all primitive recursive functions cannot be inferred with a bounded number of mind changes, again using queries in $\lbrack +, < \rbrack$. Additionally, we resolve an open question (...) in [7] about passive versus active learning. (shrink)