Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers (Q342726): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2964135541 / rank | |||
Normal rank |
Revision as of 20:32, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers |
scientific article |
Statements
Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers (English)
0 references
18 November 2016
0 references
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.
0 references
Kučera-Gács theorem
0 references
computation from random oracles
0 references
optimal redundancy bounds
0 references
betting strategies
0 references
martingales
0 references