PreprintarXiv licencearXiv
Martin-Löf randomness and rK-reducibility
Abstract
Can random real carry arbitrary information. In terms of (Turing) computability, Kučera and Gács addressed this question in affirmative. i.e., Every real x∈ 2ω is computable from some Martin-Löf random real. This result motivated quantitative versions of coding into random reals. i.e., How many bits of the random oracle are needed to compute the first n bits of x. Barmpalias and Lewis-Pye obtained a coding that uses n+O(log n) many bits. Is it possible for the coding to use n bits exactly? This is equivalent to say, if every real is rK-reducible to a Martin-Löf random real. In this paper, we prove that such a coding does not exist. i.e., There exists some real that is not rK-reducible to any Martin-Löf random real.
Related
- How far is Kolmogorov-Loveland randomness from Martin-Löf randomness?
- The Martin boundary of the Directed Landscape
- Recursive Paintboxes and the Martin Boundary of the Hoffman Rooted-Tree Graph
- Reducibility of linear representations, free ideals, and Kippenhahn's conjecture
- Reducibility and Diagonal Equality Strata for Finite Jacobi Pencils
BibTeX
@misc{barmpalias2026martinlöf,
title = {{Martin-Löf randomness and rK-reducibility}},
author = {George Barmpalias and Lu Liu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39174},
eprint = {2610.39174},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39174},
}
RIS
TY - UNPB
TI - Martin-Löf randomness and rK-reducibility
AU - George Barmpalias
AU - Lu Liu
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39174
UR - https://arxiv.org/abs/2610.39174
AB - Can random real carry arbitrary information. In terms of (Turing) computability, Kučera and Gács addressed this question in affirmative. i.e., Every real x∈ 2^ω is computable from some Martin-Löf random real. This result motivated quantitative versions of coding into random reals. i.e., How many bits of the random oracle are needed to compute the first n bits of x. Barmpalias and Lewis-Pye obtained a coding that uses n+O(log n) many bits. Is it possible for the coding to use n bits exactly? This is equivalent to say, if every real is rK-reducible to a Martin-Löf random real. In this paper, we prove that such a coding does not exist. i.e., There exists some real that is not rK-reducible to any Martin-Löf random real.
ER -