7 Classification of jump operators

The Turing jump operator xx′ is degree invariant, i.e. if xT 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 xT y via e if x = image and y = image;

–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.