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

From MaRDI portal
Import240304020342 (talk | contribs)
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
    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

    Identifiers

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