Martin-L\"of randomness and rK-reducibility
En palabras de los autores
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.
Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.