Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega

DOI10.1016/j.jcss.2016.05.004zbMath1358.03057arXiv1602.03208OpenAlexW2964310650MaRDI QIDQ736609

Nan Fang, George Barmpalias, Andrew E. M. Lewis-Pye

Publication date: 4 August 2016

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.03208

zbMATH Keywords

completenessKolmogorov complexityhalting probabilitycomputabilityoptimal asymptotic boundoracle computations

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Algorithmic randomness and dimension (03D32) Computation over the reals, computable analysis (03D78)

Related Items (4)

Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers ⋮ The Kučera-Gács theorem revisited by Levin ⋮ Kobayashi compressibility ⋮ Randomness below complete theories of arithmetic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The computable Lipschitz degrees of computably enumerable sets are not dense
• Randomness and universal machines
• Randomness and the linear degrees of computability
• A c.e. real that cannot be sw-computed by any \(\Omega\) number
• Incompleteness theorems for random reals
• Approximations to the halting problem
• Randomness and reducibility
• Analogues of Chaitin's Omega in the computably enumerable sets
• Maximal pairs of computably enumerable sets in the computably Lipschitz degrees
• The ibT degrees of computably enumerable sets are not dense
• Randomness and Recursive Enumerability
• Randomness, Computability, and Density
• A statistical mechanical interpretation of algorithmic information theory III: composite systems and fixed points
• Where Join Preservation Fails in the Bounded Turing Degrees of C.E. Sets
• Algorithmic Randomness and Complexity
• Time-Bounded Kolmogorov Complexity and Solovay Functions
• Random reals and Lipschitz continuity
• EXACT APPROXIMATIONS OF OMEGA NUMBERS
• Chaitin Ω Numbers and Halting Problems
• A Theory of Program Size Formally Identical to Information Theory
• Optimal enumerations and optimal gödel numberings
• Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees
• There is no SW-complete c.e. real
• Kolmogorov Complexity and Solovay Functions
• Computing a Glimpse of Randomness
• The definition of random sequences
• A formal theory of inductive inference. Part II
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
• New Computational Paradigms
• An introduction to Kolmogorov complexity and its applications
• Recursively enumerable reals and Chaitin \(\Omega\) numbers

This page was built for publication: Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega