# Kobayashi compressibility

arXiv: https://arxiv.org/abs/1608.00692 · HTML: https://mlsanity.com/paper/1608.00692/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Aug 2016.

## Built on by (most cited first, 1 of 1)

- [Compression of enumerations and gain](https://mlsanity.com/paper/2304.03030/) (2023)

## Abstract (arXiv)

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.