G\'acs-Ku\v{c}era's Theorem Revisited by Levin.
2021
Leonid Levin (arxiv.org/abs/cs/0503039v14, p.7) published a new (and very nice) proof of G\'acs-Ku\v{c}era's theorem that occupies only a few lines when presented in his style. We try to explain more details and discuss the connection of this proof with image randomness theorems, making explicit some result (see Proposition 4) that is implicit in Levin's exposition.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
13
References
0
Citations
NaN
KQI