Recursion Theory

7 Classification of jump operators

The Turing jump operator x ↦ x′ is degree invariant, i.e. if x ≡T y then x′ ≡T y′. The property of degree invariance is a fundamental property of the operator that motivated the introduction of Martin’s conjecture (§ 6.6.5). In this chapter we discuss a stronger one called uniform degree invariance and give a classification of functions that satisfy this property.

7.1 Uniformly degree invariant functions

Definition 7.1.1.

–If e = 〈e0, e1〉, we say that x ≡T y via e if x = and y = ;

–a function F : 2ω → 2ω is uniformly ...