Kobayashi compressibility

DOI10.1016/J.TCS.2017.02.029MaRDI QIDQ528498zbMATH OpenOpenAlexFDO

Authors George Barmpalias, Rodney G. Downey

Publication date 12 May 2017

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

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)

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.

Recommendations

• Compressibility and uniform complexity
• scientific article; zbMATH DE number 1048038
• Logical Approaches to Computational Barriers
• Every 2-random real is Kolmogorov random
• A level of Martin-Lof randomness.

Cites work

• scientific article; zbMATH DE number 512979 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 841084 (Why is no real title available?)
• scientific article; zbMATH DE number 969633 (Why is no real title available?)
• scientific article; zbMATH DE number 3307567 (Why is no real title available?)
• A Theory of Program Size Formally Identical to Information Theory
• A variant of the Kolmogorov concept of complexity
• Algorithmic randomness and complexity.
• Analogues of Chaitin's Omega in the computably enumerable sets
• Anti-complex sets and reducibilities with tiny use
• BOUNDS IN THE TURING REDUCIBILITY OF FUNCTIONS
• Bounded randomness
• Bounds in weak truth-table reducibility
• Chaitin \(\Omega \) numbers and halting problems
• Computability and randomness
• Computational power of neural networks: a characterization in terms of Kolmogorov complexity
• Computing halting probabilities from other halting probabilities
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
• Kolmogorov complexity and computably enumerable sets
• On Kurtz randomness
• Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
• Process and truth-table characterisations of randomness
• Process complexity and effective random tests
• Randomness and halting probabilities
• Randomness and recursive enumerability
• Recursively enumerable reals and Chaitin \(\Omega\) numbers
• The definition of random sequences
• \(\Sigma^ 0_ n\)-complete properties of programs and Martin-Löf randomness

Cited in

(5)

• Logical Approaches to Computational Barriers
• Compressibility and uniform complexity
• The Kučera-Gács theorem revisited by Levin
• A hierarchy of computably enumerable degrees
• Reconciling Data Compression and Kolmogorov Complexity

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)