Nies, André Lowness properties and randomness. (English) Zbl 1141.03017 Adv. Math. 197, No. 1, 274-305 (2005). Summary: The set \(A\) is low for (Martin-Löf) randomness if each random set is already random relative to \(A\). \(A\) is \(K\)-trivial if the prefix complexity \(K\) of each initial segment of \(A\) is minimal, namely \((\forall n) K(A\upharpoonright n)\leq K(n)+O(1)\). We show that these classes coincide. This answers a question of K. Ambos-Spies and A. Kučera [in: P. A. Cholak et al. (eds.), Computability theory and its applications. Current trends and open problems. Proceedings of a 1999 AMS-IMS-SIAM joint summer research conference, Boulder, CO, USA, June 13–17, 1999. Providence, RI: American Mathematical Society (AMS). Contemp. Math. 257, 1–14 (2000; Zbl 0962.03039)]: each low for Martin-Löf random set is \(\Delta^0_2\). Our class induces a natural intermediate \(\Sigma^0_3\)-ideal in the r.e. Turing degrees, which generates the whole class under downward closure.Answering a further question in [loc. cit.], we prove that each low for computably random set is computable. Cited in 7 ReviewsCited in 100 Documents MSC: 03D15 Complexity of computation (including implicit computational complexity) 03D28 Other Turing degree structures 68Q30 Algorithmic information theory (Kolmogorov complexity, etc.) Keywords:Kolmogorov prefix complexity; Randomness; \(K\)-trivial; Low for random Citations:Zbl 0962.03039 PDFBibTeX XMLCite \textit{A. Nies}, Adv. Math. 197, No. 1, 274--305 (2005; Zbl 1141.03017) Full Text: DOI References: [1] Ambos-Spies, K.; Jockusch, C. G.; Shore, R. A.; Soare, R. I., An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees, Trans. Amer. Math. Soc., 281, 109-128 (1984) · Zbl 0539.03020 [2] Ambos-Spies, K.; Kucera, A., Randomness in computability theorycurrent trend and open problem, (Cholak, P.; Lempp, S.; Lerman, M.; Shore, R., Computability Theory and Its ApplicationsCurrent Trends and Open Problems (2000), American Mathematical Society: American Mathematical Society Providence, RI) [3] A. Nies, B. Bedregal, Lowness properties of reals and hyper-immunity, in: Wollic 2003, Electronic Notes in Theoretical Computer Science, vol. 84, Elsevier, Amsterdam, 2003. http://www.elsevier.nl/locate/entcs/volume84.html; A. Nies, B. Bedregal, Lowness properties of reals and hyper-immunity, in: Wollic 2003, Electronic Notes in Theoretical Computer Science, vol. 84, Elsevier, Amsterdam, 2003. http://www.elsevier.nl/locate/entcs/volume84.html · Zbl 1264.03093 [4] C. Calude, Information and randomness, Monographs in Theoretical Computer Science, An EATCS Series. Springer, Berlin, 1994. An algorithmic perspective, With forewords by Gregory J. Chaitin and Arto Salomaa.; C. Calude, Information and randomness, Monographs in Theoretical Computer Science, An EATCS Series. Springer, Berlin, 1994. An algorithmic perspective, With forewords by Gregory J. Chaitin and Arto Salomaa. [5] Calude, C. S.; Coles, R. J., Program-size complexity of initial segments and domination reducibility, (Jewels are Forever (1999), Springer: Springer Berlin), 225-237 · Zbl 0945.68080 [6] Chaitin, G., A theory of program size formally identical to information theory, J. Assoc. Comput. Mach., 22, 329-340 (1975) · Zbl 0309.68045 [7] Chaitin, G., Information-theoretical characterizations of recursive infinite strings, Theoret. Comput. Sci., 2, 45-48 (1976) · Zbl 0328.02029 [8] Cholak, P.; Groszek, M.; Slaman, T., An almost deep degree, J. Symbolic Logic, 66, 2, 881-901 (2001) · Zbl 0992.03049 [9] R.G. Downey, D.R. Hirschfeldt, A. Nies, F. Stephan, Trivial reals, in: Proceedings of the 7th and 8th Asian Logic Conferences, Singapore University Press, Singapore, 2003, pp. 103-133.; R.G. Downey, D.R. Hirschfeldt, A. Nies, F. Stephan, Trivial reals, in: Proceedings of the 7th and 8th Asian Logic Conferences, Singapore University Press, Singapore, 2003, pp. 103-133. · Zbl 1044.03027 [10] R. Downey, D. Hirschfeldt, A. Nies, S. Terwijn, Calibrating randomness, Bull. Symbolic Logic., to appear.; R. Downey, D. Hirschfeldt, A. Nies, S. Terwijn, Calibrating randomness, Bull. Symbolic Logic., to appear. · Zbl 1113.03037 [11] D. Hirschfeldt, A. Nies, F. Stephan, Random Oracles, to appear.; D. Hirschfeldt, A. Nies, F. Stephan, Random Oracles, to appear. [12] Jockusch, C. G.; Shore, R. A., Pseudo-jump operators Ithe r.e. case, Trans. Amer. Math. Soc., 275, 599-609 (1983) · Zbl 0514.03028 [13] B. Kjos-Hanssen, F. Stephan, A. Nies, Lowness for the class of Schnorr random sets, to appear.; B. Kjos-Hanssen, F. Stephan, A. Nies, Lowness for the class of Schnorr random sets, to appear. · Zbl 1095.68043 [14] Kucera, A., On relative randomness, Ann. Pure Appl. Logic, 63, 61-67 (1993) · Zbl 0788.68068 [15] Kucera, A.; Terwijn, S., Lowness for the class of random sets, J. Symbolic Logic, 64, 1396-1402 (1999) · Zbl 0954.68080 [16] Martin-Löf, P., The definition of random sequences, Inform. and Control, 9, 602-619 (1966) · Zbl 0244.62008 [17] J. Miller, L. Yu, On initial segment complexity and degrees of randomness, to appear.; J. Miller, L. Yu, On initial segment complexity and degrees of randomness, to appear. · Zbl 1140.68028 [18] Miller, W.; Martin, D. A., The degree of hyperimmune sets, Z. Math. Logik Grundlag. Math., 14, 159-166 (1968) · Zbl 0216.29102 [19] Muchnik, A. A.; Semenov, A. L.; Uspensky, V. A., Mathematical metaphysics of randomness, Theoret. Comput. Sci., 207, 2, 263-317 (1998) · Zbl 0922.60014 [20] A. Nies, Computability and randomness, to appear.; A. Nies, Computability and randomness, to appear. · Zbl 1237.03027 [21] A. Nies, Ideals in the recursively enumerable degrees, to appear.; A. Nies, Ideals in the recursively enumerable degrees, to appear. · Zbl 1025.03031 [22] A. Nies, Reals which compute little, to appear.; A. Nies, Reals which compute little, to appear. · Zbl 1107.03047 [23] Gerald E. Sacks, Degrees of Unsolvability, Annals of Mathematical Studies, vol. 55, Princeton University Press, Princeton, NJ, 1963.; Gerald E. Sacks, Degrees of Unsolvability, Annals of Mathematical Studies, vol. 55, Princeton University Press, Princeton, NJ, 1963. · Zbl 0143.25302 [24] C.-P. Schnorr, Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie, Lecture Notes in Mathematics, vol. 218, Springer, Berlin, 1971.; C.-P. Schnorr, Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie, Lecture Notes in Mathematics, vol. 218, Springer, Berlin, 1971. [25] T.A. Slaman, Aspects of the Turing jump, in: Logic Colloquium 2000, Lecture Notes in Logic, to appear.; T.A. Slaman, Aspects of the Turing jump, in: Logic Colloquium 2000, Lecture Notes in Logic, to appear. [26] T. Slaman, R. Solovay, When oracles do not help, in: Fourth Annual Conference on Computational Learning Theory, Morgan Kaufman, Los Altos, CA, 1991, pp. 379-383.; T. Slaman, R. Solovay, When oracles do not help, in: Fourth Annual Conference on Computational Learning Theory, Morgan Kaufman, Los Altos, CA, 1991, pp. 379-383. [27] Soare, R., Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Omega Series (1987), Springer: Springer Heidelberg [28] R. Solovay, Draft of a paper (or series of papers) on chaitin’s work, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1975, 215p.; R. Solovay, Draft of a paper (or series of papers) on chaitin’s work, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1975, 215p. [29] Terwijn, S.; Zambella, D., Algorithmic randomness and lowness, J. Symbolic Logic, 66, 1199-1205 (2001) · Zbl 0990.03033 [30] D. Zambella, On sequences with simple initial segments, ILLC Technical Report ML 1990-05, University Amsterdam, 1990.; D. Zambella, On sequences with simple initial segments, ILLC Technical Report ML 1990-05, University Amsterdam, 1990. 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.