Turing degrees and randomness for continuous measures
Springer Science and Business Media LLC - Trang 1-21 - 2023
Tóm tắt
We study degree-theoretic properties of reals that are not random with respect to any continuous probability measure (NCR). To this end, we introduce a family of generalized Hausdorff measures based on the iterates of the “dissipation” function of a continuous measure and study the effective nullsets given by the corresponding Solovay tests. We introduce two constructions that preserve non-randomness with respect to a given continuous measure. This enables us to prove the existence of NCR reals in a number of Turing degrees. In particular, we show that every
$$\Delta ^0_2$$
-degree contains an NCR element.
Tài liệu tham khảo
Martin-Löf, P.: The definition of random sequences. Inf. Control 9(6), 602–619 (1966)
Zvonkin, A.K., Levin, L.A.: The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russ. Math. Surv. 25(6), 83–124 (1970)
Nies, A.: Computability and Randomness. Oxford Logic Guides, vol. 51. Oxford University Press, Oxford (2009)
Downey, R.G., Hirschfeldt, D.R.: Algorithmic Randomness and Complexity. Springer, New York (2010)
Levin, L.A.: Uniform tests of randomness. Dokl. Akad. Nauk SSSR 227(1), 33–35 (1976)
Reimann, J., Slaman, T.: Measures and their random reals. Trans. Am. Math. Soc. 367(7), 5081–5097 (2015)
Day, A., Miller, J.: Randomness for non-computable measures. Trans. Am. Math. Soc. 365(7), 3575–3591 (2013)
Montalbán, A.: Beyond the arithmetic. PhD thesis, Cornell University (2005)
Cenzer, D., Clote, P., Smith, R.L., Soare, R.I., Wainer, S.S.: Members of countable \(\Pi _1^0\) classes. Ann. Pure Appl. Logic 31, 145–163 (1986)
Barmpalias, G., Greenberg, N., Montalbán, A., Slaman, T.A.: K-trivials are never continuously random. In: Proceedings Of The 11Th Asian Logic Conference: In Honor of Professor Chong Chitat on His 60th Birthday, pp. 51–58. World Scientific (2012)
Reimann, J., Slaman, T.A.: Unpublished work (2008)
Haken, I.R.: Randomizing reals and the first-order consequences of randoms. PhD thesis, UC Berkeley (2014)
Reimann, J., Slaman, T.A.: Effective randomness for continuous measures. J. Am. Math. Soc. 35(2), 467–512 (2022)
Soare, R.I.: Turing Computability. Springer, Berlin (2016)
Li, M.: Randomness and complexity for continuous measures. PhD thesis, Pennsylvania State University (2020)
Reimann, J.: Effectively closed sets of measures and randomness. Preprint arXiv:0804.2656 (2008)
Kechris, A.S.: Classical Descriptive Set Theory. Springer, New York (1995)