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

From MaRDI portal
ReferenceBot (talk | contribs)
Changed an Item
Normalize DOI.
Property / DOI
 
Property / DOI: 10.1016/j.ic.2016.09.010 / rank
Normal rank
 
Property / DOI
 
Property / DOI: 10.1016/J.IC.2016.09.010 / rank
 
Normal rank

Revision as of 00:08, 9 December 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
    0 references
    0 references
    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
    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
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references