Randomness and the linear degrees of computability

DOI10.1016/j.apal.2006.08.001zbMath1109.03037OpenAlexW2104394421MaRDI QIDQ866567

George Barmpalias, Andrew E. M. Lewis

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

degreecomputabilityrandomness

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• A c.e. real that cannot be sw-computed by any \(\Omega\) number
• Randomness and reducibility
• Algorithmic Randomness and Complexity
• Random reals and Lipschitz continuity
• Algorithmic Information Theory
• There is no SW-complete c.e. real
• A unified approach to the definition of random sequences
• New Computational Paradigms
• Computability Theory and Differential Geometry