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.
翻译:Levin (arxiv.org/abs/cs/ 0503039v14, p.7) 公布了一份新的(非常漂亮的)G\'acs-Ku\v{c}era的理论证明, 当以他的风格显示时, 它只占据了几行。 我们试图解释更多细节, 并讨论这个证据与图像随机性理论的联系, 得出一些明确的结果( 提案4), 这在Levin的演说中是隐含的 。