Abstract
A real is called integer-valued random if no integer-valued martingale can win arbitrarily much capital betting against it. A real, A, is low for integer-valued randomness if no integer-valued martingale recursive in A can succeed on an integer-valued random real. We show that lowness for integer-valued randomness coincides with recursiveness, as is the case for computable randomness.
Get full access to this article
View all access options for this article.
References
1.G. Barmpalias R.G. Downey M. McInerney Integer valued betting strategies and Turing degrees , J. Comput. System Sci. 81 (7 ) (2015 ), 1387 –1412 .
2.B.R.C. Bedregal A. Nies Lowness properties of reals and hyper-immunity , in: WoLLIC 2003 , Vol. 84 , Elsevier , 2003 .
3.L. Bienvenu F. Stephan J. Teutsch How powerful are integer-valued martingales? , Theory Comput. Syst. 51 (3 ) (2012 ), 330 –351 .
4.R.G. Downey D.R. Hirschfeldt Algorithmic Randomness and Complexity , Theory and Applications of Computability , Springer , New York , 2010 .
5.B. Kjos-Hanssen A. Nies F. Stephan Lowness for the class of Schnorr random reals , SIAM J. Comput. 35 (3 ) (2005 ), 647 –657 .
6.A. Nies Lowness properties and randomness , Adv. Math. 197 (1 ) (2005 ), 274 –305 .
7.A. Nies Computability and Randomness , Oxford Logic Guides , Vol. 51 , Oxford Univ. Press , Oxford , 2009 .
8.C.-P. Schnorr A unified approach to the definition of random sequences , Math. Systems Theory 5 (1971 ), 246 –258 .