Oracles and Turing degrees

Oracle machines and the use principle, Turing reducibility and the upper semilattice of Turing degrees, the Turing jump and its iterates, Shoenfield's limit lemma and the sets computable in the halting problem, constructions by finite extensions (incomparable degrees, cone avoidance, 1-generic sets), and the low and high sets.

Contents

1. 1

   Computation relative to an oracle

   Oracle machines, Turing functionals, computations with finite oracles and the use principle; relativization of the universal function and of the SMN theorem.

   1. 1.1 Strings and sequences
   2. 1.2 Oracle machines
   3. 1.3 Computations with finite oracles
   4. 1.4 Relativization
   5. 1.5 Oracles that are functions
   6. 1.6 Exercises
   7. 1.7 Notes and references
   40 min
2. 2

   Turing reducibility and degrees

   Turing reducibility, the partial order of Turing degrees, the join as least upper bound, countability of lower cones, and relative computable enumerability.

   1. 2.1 Turing reducibility
   2. 2.2 Turing degrees
   3. 2.3 The join
   4. 2.4 Relative enumerability
   5. 2.5 Exercises
   6. 2.6 Notes and references
   35 min
3. 3

   The Turing jump

   The jump of a set, its completeness for relatively c.e. sets, its strict increase and monotonicity, the iterated jumps, and the position of totality and finiteness below the double jump.

   1. 3.1 Definition
   2. 3.2 Properties of the jump
   3. 3.3 Complete sets
   4. 3.4 Totality and finiteness
   5. 3.5 Exercises
   6. 3.6 Notes and references
   35 min
4. 4

   Limit computability

   Shoenfield's limit lemma; Δ⁰₂ approximations, their moduli and computation functions; domination properties of the sets computable in ∅′.

   1. 4.1 Limit computable sets
   2. 4.2 Moduli and computation functions
   3. 4.3 Exercises
   4. 4.4 Notes and references
   40 min
5. 5

   The finite extension method

   Constructions by finite extensions; the Kleene–Post theorem on incomparable degrees below 0′; avoiding the cone above a non-computable set; 1-generic sets.

   1. 5.1 Dense sets of strings
   2. 5.2 Incomparable degrees
   3. 5.3 Avoiding a cone
   4. 5.4 1-generic sets
   5. 5.5 Exercises
   6. 5.6 Notes and references
   45 min
6. 6

   Low and high sets

   Sets whose jump is as small or as large as possible; 1-generic sets are generalized low, so non-computable low sets exist; high sets that avoid a cone.

   1. 6.1 Low sets
   2. 6.2 High sets
   3. 6.3 Exercises
   4. 6.4 Notes and references
   40 min