Randomness and the linear degrees of computability

DOI10.1016/J.APAL.2006.08.001MaRDI QIDQ866567zbMATH OpenOpenAlexFDO

Authors Andrew E. M. Lewis, George Barmpalias

Publication date 14 February 2007

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.apal.2006.08.001

zbMATH Keywords

degreerandomnesscomputability

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• Randomness, lowness and degrees
• Maximal pairs of c.e. reals in the computably Lipschitz degrees
• Randomness, computability, and density
• The Kolmogorov complexity of random reals
• scientific article; zbMATH DE number 1688364

Cites work

• scientific article; zbMATH DE number 4008384 (Why is no real title available?)
• scientific article; zbMATH DE number 1834658 (Why is no real title available?)
• A c.e. real that cannot be sw-computed by any \(\Omega\) number
• A unified approach to the definition of random sequences
• Algorithmic Information Theory
• Algorithmic randomness and complexity.
• Computability Theory and Differential Geometry
• New Computational Paradigms
• Random reals and Lipschitz continuity
• Randomness and reducibility
• There is no SW-complete c.e. real

Cited in

(19)

• Sub-computable Boundedness Randomness
• Randomness below complete theories of arithmetic
• Lowness, Randomness, and Computable Analysis
• Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers
• Working with strong reducibilities above totally \(\omega \)-c.e. and array computable degrees
• The ibT degrees of computably enumerable sets are not dense
• Rank and randomness
• Maximal pairs of computably enumerable sets in the computably Lipschitz degrees
• Structures of some strong reducibilities
• Some Questions in Computable Mathematics
• Random reals and Lipschitz continuity
• On randomness, determinism and computability
• The method of the Yu–Ding Theorem and its application
• A uniform version of non-\(\mathrm{low}_{2}\)-ness
• Non-low\(_2\)-ness and computable Lipschitz reducibility
• Bounded Turing reductions and data processing inequalities for sequences
• Lines missing every random point
• Maximal pairs of c.e. reals in the computably Lipschitz degrees
• Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega

This page was built for publication: Randomness and the linear degrees of computability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q866567)