Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers
From MaRDI portal
Publication:342726
DOI10.1016/j.ic.2016.09.010zbMath1354.03056arXiv1602.07113OpenAlexW2964135541MaRDI QIDQ342726
Jason Teutsch, George Barmpalias, Andrew E. M. Lewis-Pye
Publication date: 18 November 2016
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1602.07113
martingalesbetting strategiescomputation from random oraclesKučera-Gács theoremoptimal redundancy bounds
Generalizations of martingales (60G48) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Probabilistic games; gambling (91A60) Algorithmic randomness and dimension (03D32)
Related Items
Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers, Optimal redundancy in computations from random oracles, The Kučera-Gács theorem revisited by Levin, Granularity of wagers in games and the possibility of saving
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers
- How to build a probability-free casino
- How powerful are integer-valued martingales?
- Kolmogorov complexity of initial segments of sequences and arithmetical definability
- Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
- Randomness and the linear degrees of computability
- How to gamble against all odds
- Effective martingales with restricted wagers
- A savings paradox for integer-valued gambling strategies
- Integer valued betting strategies and Turing degrees
- Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
- Algorithmic Randomness and Complexity
- Chaitin Ω Numbers and Halting Problems
- Every sequence is reducible to a random one
- On the construction of effectively random sets
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
- A unified approach to the definition of random sequences
- The definition of random sequences
- Lowness for integer-valued randomness
- Logical Approaches to Computational Barriers
