{"id":"arxiv/2610.39174","url":"https://arxiv.org/abs/2610.39174","tags":["math.LO"],"score":0,"title":"Martin-Löf randomness and rK-reducibility","domain":"math.LO","source":"arxiv","authors":["George Barmpalias","Lu Liu"],"reviews":0,"subject":"math.LO","summary":"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\\in 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.…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-29","reactions":{}}