Gacs-Kucera Theorem
arXiv:2207.12489 · doi:10.1016/j.tcs.2022.06.040
Abstract
Gacs-Kucera Theorem, tightened by Barmpalias and Lewis-Pye, w.t.t.-reduces each infinite sequence to a Kolmogorov--Martin-Lof random one and is broadly used in various Math and CS areas. Its early proofs are somewhat cumbersome, but using some general concepts yields significant simplification illustrated here.
1 page. Theoretical Computer Science, 2022