Bounded Queries in Recursion Theory

A: Getting Your Feet Wet.- 1 Basic Concepts.- 1.1 Notation, Conventions, and Definitions.- 1.2 Basic Recursion Theory.- 1.2.1 Recursive and Recursively Enumerable Sets.- 1.2.2 Reductions.- 1.2.3 Jump and the Arithmetic Hierarchy.- 1.2.4 Simulation and Dovetailing.- 1.3 Useful Concepts from Recursion Theory.- 1.3.1 The Recursion Theorem.- 1.3.2 Initial Segment Arguments.- 1.4 Advanced Concepts We Will Need.- 1.5 Exercises.- 1.6 Bibliographic Notes.- 2 Bounded Queries and the Halting Set.- 2.1 Basic Results About K.- 2.2 Exercises.- 2.3 Bibliographic Notes.- 3 Definitions and Questions.- 3.1 Definitions of Classes.- 3.2 Questions We Address.- 3.3 Enumerability and Bounded Queries.- 3.4 Uniformity.- 3.5 Order Notation.- 3.6 Exercises.- 3.7 Bibliographic Notes.- B: The Complexity of Functions.- 4 The Complexity of CnA.- 4.1 A General Lower Bound.- 4.2 Class Separation: FQ(n,A) ? FQ(n+ 1,A).- 4.3 Verbose Sets.- 4.4 Non-superterse Sets Are Semiverbose.- 4.5 Superterse Sets.- 4.6 Semiverbose Sets.- 4.7 Most Sets Are Superterse.- 4.7.1 The Set of Superterse Sets Has Measure 1.- 4.7.2 The Set of Superterse Sets Is Co-meager.- 4.8 Recursively Enumerable Sets.- 4.8.1 Using Queries to Other Sets.- 4.8.2 Using Queries to A.- ...