zbMATH — the first resource for mathematics

Schnorr trivial reals: a construction. (English) Zbl 1142.03020
Summary: A real is Martin-Löf (Schnorr) random if it does not belong to any effectively presented null \({\Sigma^0_1}\) (recursive) class of reals. Although these randomness notions are very closely related, the set of Turing degrees containing reals that are \(K\)-trivial has very different properties from the set of Turing degrees that are Schnorr trivial. A. Nies proved in [Adv. Math. 197, No. 1, 274–305 (2005; Zbl 1141.03017)] that all \(K\)-trivial reals are low. In this paper, we prove that if \({{\mathbf h'} \geq_T {\mathbf 0''}}\), then h contains a Schnorr trivial real. Since this concept appears to separate computational complexity from computational strength, it suggests that Schnorr trivial reals should be considered in a structure other than the Turing degrees.

03D15 Complexity of computation (including implicit computational complexity)
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
Full Text: DOI
[1] Chaitin, G.J.: A theory of program size formally identical to information theory. J. Assoc. Comput. Mach. 22, 329–340 (1975) · Zbl 0309.68045
[2] Chaitin, G.J.: Algorithmic information theory. IBM J. Res. Develop. 21(4), 350–359 (1977) · Zbl 0362.94035 · doi:10.1147/rd.214.0350
[3] Downey, R., Griffiths, E., Laforte, G.: On Schnorr and computable randomness, martingales, and machines. Math. Log. Q. 50(6), 613–627 (2004) · Zbl 1062.68064 · doi:10.1002/malq.200310121
[4] Downey, R., Hirschfeldt, D.R., Nies, A., Terwijn, S.A.: Calibrating randomness. Bull. Symb. Logic 12(3), 411–491 (2006) · Zbl 1113.03037 · doi:10.2178/bsl/1154698741
[5] Downey, R.G., Griffiths, E.J.: Schnorr randomness. J. Symb. Logic 69(2), 533–554 (2004) · Zbl 1072.03025 · doi:10.2178/jsl/1082418542
[6] Downey, R.G., Hirschfeldt, D.R., Nies, A., Stephan, F.: Trivial reals. In: Proceedings of the 7th and 8th Asian Logic Conferences, pp. 103–131. Singapore University Press, Singapore (2003) · Zbl 1044.03027
[7] Franklin, J.N.Y.: Hyperimmune-free degrees and Schnorr triviality. Submitted · Zbl 1181.03045
[8] Kjos-Hanssen, B., Nies, A., Stephan, F.: Lowness for the class of Schnorr random reals. SIAM J. Comput. 35(3), 647–657 (2005) (electronic) · Zbl 1095.68043 · doi:10.1137/S0097539704446323
[9] Kučera, A.: Measure, \({\Pi^{0}_{1}}\) -classes and complete extensions of PA. In: Recursion theory week (Oberwolfach, 1984). Lecture Notes in Mathematics, vol. 1141, pp. 245–259. Springer, Berlin (1985)
[10] Martin-Löf, P.: The definition of random sequences. Inform. Control 9, 602–619 (1966) · Zbl 0244.62008 · doi:10.1016/S0019-9958(66)80018-9
[11] Miller, W., Martin, D.A.: The degrees of hyperimmune sets. Z. Math. Logik Grundlagen Math. 14, 159–166 (1968) · Zbl 0216.29102 · doi:10.1002/malq.19680140704
[12] Nies, A.: Lowness properties and randomness. Adv. Math. 197(1), 274–305 (2005) · Zbl 1141.03017 · doi:10.1016/j.aim.2004.10.006
[13] Nies, A., Stephan, F., Terwijn, S.A.: Randomness, relativization and Turing degrees. J. Symb. Logic 70(2), 515–535 (2005) · Zbl 1090.03013 · doi:10.2178/jsl/1120224726
[14] Schnorr, C.P.: A unified approach to the definition of random sequences. Math. Syst. Theory 5, 246–258 (1971) · Zbl 0227.62005 · doi:10.1007/BF01694181
[15] Terwijn, S.A., Zambella, D.: Computational randomness and lowness. J. Symb. Logic 66(3), 1199–1205 (2001) · Zbl 0990.03033 · doi:10.2307/2695101
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.