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

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

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

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 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)

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.

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

Cites work

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

Cited in

(5)

• Randomness below complete theories of arithmetic
• 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
• Chaitin's halting probability and the compression of strings using oracles
• 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)