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

DOI10.1016/J.JCSS.2016.05.004zbMATH Open1358.03057arXiv1602.03208OpenAlexW2964310650MaRDI QIDQ736609FDOQ736609

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

Publication date: 4 August 2016

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

Abstract: Chaitin's number Omega is the halting probability of a universal prefix-free machine, and although it depends on the underlying enumeration of prefix-free machines, it is always Turing-complete. It can be observed, in fact, that for every computably enumerable (c.e.) real, there exists a Turing functional via which Omega computes it, and such that the number of bits of omega that are needed for the computation of the first n bits of the given number (i.e. the use on argument n) is bounded above by a computable function h(n) = n+o(n). We characterise the asymptotic upper bounds on the use of Chaitin's omega in oracle computations of halting probabilities (i.e. c.e. reals). We show that the following two conditions are equivalent for any computable function h such that h(n)-n is non-decreasing: (1) h(n)-n is an information content measure, (2) for every c.e. real there exists a Turing functional via which omega computes the real with use bounded by h. We also give a similar characterisation with respect to computations of c.e. sets from Omega, by showing that the following are equivalent for any computable non-decreasing function g: (1) g is an information-content measure, (2) for every c.e. set A, Omega computes A with use bounded by g. Further results and some connections with Solovay functions are given.

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

Recommendations

• Chaitin \(\Omega \) numbers and halting problems
• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• Chaitin's halting probability and the compression of strings using oracles
• Computing halting probabilities from other halting probabilities
• Recursively enumerable reals and Chaitin \(\Omega\) numbers

zbMATH Keywords

completenessKolmogorov complexitycomputabilityhalting probabilityoptimal asymptotic boundoracle computations

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

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

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

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