Martin-Löf randomness and rK-reducibility
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.…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.39174
curl -X POST /api/v1/records/arxiv/2610.39174/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.39174/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'