Kobayashi compressibility

DOI10.1016/J.TCS.2017.02.029zbMATH Open1369.68249arXiv1608.00692OpenAlexW4206371891MaRDI QIDQ528498FDOQ528498

Rodney G. Downey, George Barmpalias

Publication date: 12 May 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Kobayashi introduced a uniform notion of compressibility of infinite binary sequences in terms of relative Turing computations with sub-identity use of the oracle. Kobayashi compressibility has remained a relatively obscure notion, with the exception of some work on resource bounded Kolmogorov complexity. The main goal of this note is to show that it is relevant to a number of topics in current research on algorithmic randomness. We prove that Kobayashi compressibility can be used in order to define Martin-Loef randomness, a strong version of finite randomness and Kurtz randomness, strictly in terms of Turing reductions. Moreover these randomness notions naturally correspond to Turing reducibility, weak truth-table reducibility and truth-table reducibility respectively. Finally we discuss Kobayashi's main result from his 1981 technical report regarding the compressibility of computably enumerable sets, and provide additional related original results.

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

zbMATH Keywords

Kolmogorov complexityrandomnessKobayashi compressibilityuniform reductions

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithmic Randomness and Complexity
• Process complexity and effective random tests
• A Theory of Program Size Formally Identical to Information Theory
• The definition of random sequences
• A variant of the Kolmogorov concept of complexity
• Chaitin Ω Numbers and Halting Problems
• Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
• Analogues of Chaitin's Omega in the computably enumerable sets
• Kolmogorov complexity and computably enumerable sets
• BOUNDS IN THE TURING REDUCIBILITY OF FUNCTIONS
• Computational power of neural networks: a characterization in terms of Kolmogorov complexity
• Randomness and recursive enumerability
• Anti-Complex Sets and Reducibilities with Tiny Use
• Bounds in weak truth-table reducibility
• \(\Sigma^ 0_ n\)-complete properties of programs and Martin-Löf randomness
• On Kurtz randomness
• Bounded Randomness
• Randomness and halting probabilities
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
• Recursively enumerable reals and Chaitin \(\Omega\) numbers
• Process and truth-table characterisations of randomness
• Computing halting probabilities from other halting probabilities

Cited In (2)

• The Kučera-Gács theorem revisited by Levin
• A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES

This page was built for publication: Kobayashi compressibility

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