pipette
ESEspañol

Martin-L\"of randomness and rK-reducibility

George Barmpalias, Lu Liu

Preprint

In the authors' words

Can random real carry arbitrary information. In terms of (Turing) computability, Ku\v{c}era and G\'{a}cs addressed this question in affirmative. i.e., Every real is computable from some Martin-L\"of 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 bits of . Barmpalias and Lewis-Pye obtained a coding that uses many bits. Is it possible for the coding to use bits exactly? This is equivalent to say, if every real is -reducible to a Martin-L\"of random real. In this paper, we prove that such a coding does not exist. i.e., There exists some real that is not -reducible to any Martin-L\"of random real.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.