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 ...
Get Recursion Theory now with the O’Reilly learning platform.
O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.