Extending CL-reducibility on array noncomputable degrees
The paper studies refinements of Turing reducibility for left-c.e.\ reals in algorithmic randomness, focusing on bounded-use reducibilities of the form \((\mathrm{id}+g)\)-bT. These generalize computably Lipschitz (cl) reducibility by allowing a computable nondecreasing overhead function \(g\).\N\NPrevious work showed that two classical cl-reducibility theorems characterize array noncomputable c.e.\ degrees: the existence of maximal pairs of left-c.e.\ reals and the existence of a left-c.e.\ real not reducible to any random left-c.e.\ real. The first theorem has been extended to \((\mathrm{id}+g)\)-bT whenever \(g\) is slow-growing. This paper proves that the second theorem can also be extended analogously, thereby completing the corresponding extension program. This yields a clear dichotomy between slow-growing and fast-growing use bounds.\N\NA technical contribution of the paper is a simplified construction method for left-c.e.\ reals based on global ``loading arguments, replacing more involved game-based priority constructions from the literature. This leads to shorter proofs and a unified treatment of several known results.\N\NThe paper is technically solid and contributes to a better structural understanding of bounded reducibilities and array noncomputable degrees. The exposition is clear for readers familiar with computability and algorithmic randomness, and the discussion of open problems is useful.
- A c.e. real that cannot be sw-computed by any \(\Omega\) number
- Algorithmic randomness and complexity.
- Computing halting probabilities from other halting probabilities
- Every sequence is reducible to a random one
- scientific article; zbMATH DE number 4172959 (Why is no real title available?)
- scientific article; zbMATH DE number 4008384 (Why is no real title available?)
- scientific article; zbMATH DE number 841084 (Why is no real title available?)
- Limits of the Kučera–Gács Coding Method
- Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers
- Maximal pairs of c.e. reals in the computably Lipschitz degrees
- On the construction of effectively random sets
- Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
- Optimal redundancy in computations from random oracles
- The Kučera-Gács theorem revisited by Levin
- There is no SW-complete c.e. real
- Working with strong reducibilities above totally -c.e. and array computable degrees
This page was built for publication: Extending CL-reducibility on array noncomputable degrees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7021348)
