Extending CL-reducibility on array noncomputable degrees

Given a function f, f-bounded-Turing (f-bT-) reducibility is the Turing reducibility with use function bounded by f. In the special case where f = id + c (with id being the identity function and c a constant), this is referred to as cl-reducibility. In a work by Barmpalias, Fang, and Lewis-Pye, it was proven that there exist two left-c. e. reals such that no left-c. e. real ( id + g ) -bT-computes both of them whenever g is computable, nondecreasing, and satisfies ∑ n 2 − g ( n ) = ∞. Moreover, such maximal pairs exist precisely within every array noncomputable degree. This result generalizes a prior result on cl-reducibility, which states that there exist two left-c. e. reals such that no left-c. e. real cl-computes both of them. An open question remained as to whether a similar extension could apply to another result on cl-reducibility, which asserts that there exists a left-c. e. real not cl-reducible to any random left-c. e. real. We answer this question affirmatively, providing a simpler proof compared to previous works. Additionally, we streamline the proof of the initial extension.

Authors

• Nan Fang
• Wolfgang Merkle

Keywords

No keywords are indexed for this paper.