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 p...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
28 November 2024
|
| In: |
Information and computation
Year: 2025, Volume: 303, Pages: 1-11 |
| ISSN: | 1090-2651 |
| DOI: | 10.1016/j.ic.2024.105258 |
| Online Access: | Verlag, kostenfrei, Volltext: https://doi.org/10.1016/j.ic.2024.105258 Verlag, kostenfrei, Volltext: https://www.sciencedirect.com/science/article/pii/S0890540124001238 
|
| Author Notes: | Nan Fang, Wolfgang Merkle |
| Summary: | 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 ∑n2−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. |
|---|---|
| Item Description: | Gesehen am 25.08.2025 |
| Physical Description: | Online Resource |
| ISSN: | 1090-2651 |
| DOI: | 10.1016/j.ic.2024.105258 |