Oreals with _2⁰-bounded complexity and compressive power

DOI10.1017/JSL.2015.68zbMATH Open1364.03061arXiv1410.3615OpenAlexW2520901609MaRDI QIDQ2976366FDOQ2976366

Authors: Ian Herbert 

Publication date: 28 April 2017

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Abstract: The (prefix-free) Kolmogorov complexity of a finite binary string is the length of the shortest description of the string. This gives rise to some `standard' lowness notions for reals: A is K-trivial if its initial segments have the lowest possible complexity and A is low for K if using A as an oracle does not decrease the complexity of strings by more than a constant factor. We weaken these notions by requiring the defining inequalities to hold up only up to all $Delt{a}_2^0$ orders, and call the new notions $Delt{a}_2^0$-bounded K-trivial and $Delt{a}_2^0$-bounded low for K. Several of the `nice' properties of K-triviality are lost with this weakening. For instance, the new weaker definitions both give uncountable set of reals. In this paper we show that the weaker definitions are no longer equivalent, and that the $Delt{a}_2^0$-bounded K-trivials are cofinal in the Turing degrees. We then compare them to other previously studied weakenings, namely infinitely-often K-triviality and weak lowness for K (in each, the defining inequality must hold up to a constant, but only for infinitely many inputs). We show that $Delt{a}_2^0$-bounded K-trivial implies infinitely-often K-trivial, but no implication holds between $Delt{a}_2^0$-bounded low for K and weakly low for K.

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

Recommendations

• Being low along a sequence and elsewhere
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• Incompleteness, approximation and relative randomness
• On the gap between trivial and nontrivial initial segment prefix-free complexity
• Kolmogorov complexity of initial segments of sequences and arithmetical definability

zbMATH Keywords

Kolmogorov complexityalgorithmic randomness\(K\)-triviality

Mathematics Subject Classification ID

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

Cites Work

• Computability and randomness
• Lowness properties and randomness
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• Kolmogorov complexity of initial segments of sequences and arithmetical definability
• Information-theoretic characterizations of recursive infinite strings
• Randomness and reducibility
• The Kolmogorov complexity of random reals
• On the gap between trivial and nontrivial initial segment prefix-free complexity
• Chaitin's halting probability and the compression of strings using oracles

This page was built for publication: Oreals with \(\Delta_2^0\)-bounded complexity and compressive power

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