The Kučera–Gács theorem revisited by Levin
Abstract
Leonid Levin (https://arxiv.org/abs/cs/0503039v14) published a new (and very nice) proof of the Kučera–Gács 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 that is implicit in Levin's paper. 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.
Origin | Files produced by the author(s) |
---|