Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers (Q342726): Difference between revisions

Kucera-Gacs theorem says that every real is Turing computed by a random real using the function \(n+h(h)\), where \(h(n)\) is some nondecreasing computable function. In this very interesting paper, a lower bound on \(h\) is provided, i.e. there is a real \(x\) so that \(\sum_n 2{-h(n)} <\infty\) for every nondecreasing computable function \(h\) for which there exists a random real \(g\) which computes \(x\) using the function \(n+h(n)\). Moreover, such \(x\) can be computed by an arbitrary \(\mathrm{non-low}_2\) real.