On Kurtz randomness. (English) Zbl 1070.68054
Summary: Kurtz randomness is a notion of algorithmic randomness for real numbers. In particular a real is called Kurtz random (or weakly random) iff it is contained in every computably enumerable set \(U\) of (Lebesgue) measure 1. We prove a number of characterizations of this notion, relating it to other notions of randomness such as the well-known notions of computable randomness, Martin-Löf randomness and Schnorr randomness. For the first time we give machine characterizations of Kurtz randomness. Whereas the Turing degree of every Martin-Löf random c.e. real is the complete degree, and the degrees of Schnorr random c.e. reals are all high, we show that Kurtz random c.e. reals occur in every non-zero c.e. degree. Additionally, we show that the sets that are low for Kurtz randomness are all hyperimmune and include those that are low for Schnorr randomness, characterized previously by Terwijn and Zambella.
MSC:
| 68Q30 | Algorithmic information theory (Kolmogorov complexity, etc.) |
| 03D25 | Recursively (computably) enumerable sets and degrees |
| 03D80 | Applications of computability and recursion theory |
References:
| [1] | K. Ambos-Spies, A. Kučera, Randomness in computability theory, in: P. Cholak, S. Lempp, M. Lerman, R. Shore (Eds.), Computability Theory and its Applications, Contemporary Mathematics, vol. 257, 2000, pp. 1-14.; K. Ambos-Spies, A. Kučera, Randomness in computability theory, in: P. Cholak, S. Lempp, M. Lerman, R. Shore (Eds.), Computability Theory and its Applications, Contemporary Mathematics, vol. 257, 2000, pp. 1-14. · Zbl 0962.03039 |
| [2] | C. Calude, P. Hertling, B. Khoussainov, Y. Wang, Recursively enumerable reals and Chaitin’s \(Ω\); C. Calude, P. Hertling, B. Khoussainov, Y. Wang, Recursively enumerable reals and Chaitin’s \(Ω\) · Zbl 0894.68081 |
| [3] | Chaitin, G., A theory of program size formally identical to information theory, J. Assoc. Comput. Mach., 22, 329-340 (1975) · Zbl 0309.68045 |
| [4] | R. Downey, E. Griffiths, On Schnorr randomness, J. Symbolic Logic, to appear.; R. Downey, E. Griffiths, On Schnorr randomness, J. Symbolic Logic, to appear. · Zbl 1261.03134 |
| [5] | R. Downey, E. Griffiths, G. LaForte, On Schnorr and computable randomness, martingales, and machines, Math. Logic Quart., to appear.; R. Downey, E. Griffiths, G. LaForte, On Schnorr and computable randomness, martingales, and machines, Math. Logic Quart., to appear. · Zbl 1062.68064 |
| [6] | R. Downey, D. Hirschfeldt, A. Nies, J. Miller, On \(Ω^A\); R. Downey, D. Hirschfeldt, A. Nies, J. Miller, On \(Ω^A\) |
| [7] | R. Downey, D. Hirschfeldt, Algorithmic Randomness and Complexity, Springer, Berlin, to appear.; R. Downey, D. Hirschfeldt, Algorithmic Randomness and Complexity, Springer, Berlin, to appear. · Zbl 1221.68005 |
| [8] | Downey, R.; Hirschfeldt, D.; Nies, A., Randomness, computability and density, SIAM J. Comput., 31, 1169-1183 (2002), (Extended abstract appeared in: A. Ferriera, H. Reichel (Eds.), Symp. Theoretical Aspects of Computer Science, STACS’01 January, 2001, Lecture Notes in Computer Science, Springer, Berlin, 2001, pp. 195-201) · Zbl 1052.68060 |
| [9] | R. Downey, D. Hirschfeldt, A. Nies, F. Stephan, Trivial reals, extended abstract, in: B. Schröder (Eds.), Computability and Complexity in Analysis Malaga (Electronic Notes in Theoretical Computer Science, and proceedings, Weihrauch, FernUniversität, 294-6/2002, July 2002, pp. 37-55. Final version appears in: Proc. 7th and 8th Asian Logic Conferences, World Scientific, Singapore, 2003, pp. 103-131).; R. Downey, D. Hirschfeldt, A. Nies, F. Stephan, Trivial reals, extended abstract, in: B. Schröder (Eds.), Computability and Complexity in Analysis Malaga (Electronic Notes in Theoretical Computer Science, and proceedings, Weihrauch, FernUniversität, 294-6/2002, July 2002, pp. 37-55. Final version appears in: Proc. 7th and 8th Asian Logic Conferences, World Scientific, Singapore, 2003, pp. 103-131). |
| [10] | S. Kautz, Degrees of random sets, Ph.D. Dissertation, Cornell, 1991.; S. Kautz, Degrees of random sets, Ph.D. Dissertation, Cornell, 1991. |
| [11] | B. Kjos-Hanssen, A. Nies, F. Stephan, On a question of Ambos-Spies and Kučera, to appear.; B. Kjos-Hanssen, A. Nies, F. Stephan, On a question of Ambos-Spies and Kučera, to appear. · Zbl 1095.68043 |
| [12] | A. Kučera, Measure \(Π^0_1\); A. Kučera, Measure \(Π^0_1\) |
| [13] | Kučera, A.; Slaman, T., Randomness and recursive enumerability, SIAM J. Comput., 31, 199-211 (2001) · Zbl 0992.68079 |
| [14] | Kučera, A.; Terwijn, S., Lowness for the class of random sets, J. Symbolic Logic, 64, 1396-1402 (1999) · Zbl 0954.68080 |
| [15] | Kurtz, S., Notions of weak genericity, J. Symbolic Logic, 48, 764-770 (1983) · Zbl 0549.03042 |
| [16] | S. Kurtz, Randomness and genericity in the degrees of unsolvability, Ph.D. Thesis, University of Illinois at Urbana, 1981.; S. Kurtz, Randomness and genericity in the degrees of unsolvability, Ph.D. Thesis, University of Illinois at Urbana, 1981. |
| [17] | Levin, L. A., On the notion of a random sequence, Soviet Math. Dokl., 14, 1413-1416 (1973) · Zbl 0312.94006 |
| [18] | Levy, P., Theorie de l’Addition des Variables Aleantoires (1937), Gauthier-Villars: Gauthier-Villars Paris · JFM 63.0490.04 |
| [19] | Li, Ming, P. Vitanyi, Kolmogorov Complexity and its Applications, Springer, Berlin, 1993.; Li, Ming, P. Vitanyi, Kolmogorov Complexity and its Applications, Springer, Berlin, 1993. · Zbl 0805.68063 |
| [20] | Martin-Löf, P., The definition of random sequences, Inform. Control, 9, 602-619 (1966) · Zbl 0244.62008 |
| [21] | A. Nies, Reals which compute little, submitted.; A. Nies, Reals which compute little, submitted. · Zbl 1107.03047 |
| [22] | A. Nies, Lowness properties of reals and randomness, in preparation.; A. Nies, Lowness properties of reals and randomness, in preparation. · Zbl 1141.03017 |
| [23] | B. Kjos-Hanssen, F. Stephan, A. Nies, On a question of Ambos-Spies and Kučera, to appear.; B. Kjos-Hanssen, F. Stephan, A. Nies, On a question of Ambos-Spies and Kučera, to appear. · Zbl 1095.68043 |
| [24] | Schnorr, C. P., Zufälligkeit und Wahrscheinlichkeit, Lecture Notes in Mathematics, vol. 218 (1971), Springer: Springer Berlin · Zbl 0232.60001 |
| [25] | Schnorr, C. P., A unified approach to the definition of a random sequence, Math. Systems Theory, 5, 246-258 (1971) · Zbl 0227.62005 |
| [26] | C.P. Schnorr, A survey of the theory of random sequences, in: Basic Problems in Methodology and Linguistics, D. Reidel, Dordrecht, Holland, 1977, pp. 193-210.; C.P. Schnorr, A survey of the theory of random sequences, in: Basic Problems in Methodology and Linguistics, D. Reidel, Dordrecht, Holland, 1977, pp. 193-210. |
| [27] | Soare, R., Recursively Enumerable Sets and Degrees (1987), Springer: Springer Berlin · Zbl 0623.03042 |
| [28] | Terwijn, S.; Zambella, D., Algorithmic randomness and lowness, J. Symbolic Logic, 66, 1199-1205 (2001) · Zbl 0990.03033 |
| [29] | M. van Lambalgen, Random sequences, Ph.D. Dissertation, University of Amsterdam, 1987.; M. van Lambalgen, Random sequences, Ph.D. Dissertation, University of Amsterdam, 1987. · Zbl 0628.60001 |
| [30] | Ville, J., Ětude Critique de la Concept du Collectif (1939), Gauthier-Villars: Gauthier-Villars Paris · JFM 65.0547.05 |
| [31] | von Mises, R., Grundlagen der Wahrscheinlichkeitsrechnung, Math. Z., 5, 52-99 (1919) · JFM 47.0483.01 |
| [32] | Y. Wang, Randomness and complexity, Ph.D. Dissertation, University of Heidelberg, 1996.; Y. Wang, Randomness and complexity, Ph.D. Dissertation, University of Heidelberg, 1996. · Zbl 0858.03041 |
| [33] | Weihrauch, K., Computability (1987), Springer: Springer Berlin · Zbl 0611.03002 |
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.
