Randomness and the linear degrees of computability

DOI10.1016/J.APAL.2006.08.001zbMATH Open1109.03037OpenAlexW2104394421MaRDI QIDQ866567FDOQ866567

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

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
• Publication:2762505

zbMATH Keywords

degreerandomnesscomputability

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (19)

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

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)