


















Leonid Levin (arxiv.org/abs/cs/0503039v14, p.7) published a new (and very nice) proof of Gács-Kuč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. Then we review the previous work about the oracle use when reducing a given sequence to another one, and its connection with algorithmic dimension theory.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。