Kobayashi compressibility

Kobayashi [21] introduced a uniform notion of compressibility of infinite binary sequences X in terms of relative Turing computations with sub-identity use of the oracle. Given f:N→N we say that X is f-compressible if there exists Y such that for each n we compute X↾n using at most the first f(n) bi...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2017-05, Vol.675, p.89-100
Main Authors: Barmpalias, George, Downey, Rodney G.
Format: Article
Language:English
Subjects:
Compressibility
Kobayashi
Kolmogorov complexity
Randomness
Uniform reductions
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Kobayashi [21] introduced a uniform notion of compressibility of infinite binary sequences X in terms of relative Turing computations with sub-identity use of the oracle. Given f:N→N we say that X is f-compressible if there exists Y such that for each n we compute X↾n using at most the first f(n) bits of the oracle Y. 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-Löf 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 [21] regarding the compressibility of computably enumerable sets, and provide additional related original results.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2017.02.029