×

Kolmogorov-Loveland randomness and stochasticity. (English) Zbl 1097.03041

In the paper under review the authors prove that for every effective split of a Kolmogorov-Loveland random sequence at least one of the parts is Martin-Löf random. It follows that every Kolmogorov-Loveland random sequence has arbitrarily dense subsequences that are Martin-Löf random. This result gives a partial answer to a well-known open problem in the field of effective randomness, that is, whether Martin-Löf randomness is the same as Kolmogorov-Loveland randomness.
However, the authors also construct a sequence that is not even computably random such that every effective split yields two subsequences that are 2-random. This means that the splitting property does not characterize Kolmogorov-Loveland randomness. Moreover, the authors prove that for any Kolmogorov-Loveland random sequence \(A\) which is Turing reducible to the halting problem, the following holds: for any effective split of \(A\) both its parts are Martin-Löf random, and for any computable nondecreasing and nonbounded function \(g\) and almost all integers \(n\), the prefix of \(A\) of length \(n\) has prefix-free Kolmogorov complexity at least \(n-g(n)\).

MSC:

03D80 Applications of computability and recursion theory
03D25 Recursively (computably) enumerable sets and degrees
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ambos-Spies, K.; Kučera, A., Randomness in computability theory, (Computability Theory and its Applications (Boulder, CO, 1999). Computability Theory and its Applications (Boulder, CO, 1999), Contemp. Math., vol. 257 (2000), Amer. Math. Soc.), 1-14 · Zbl 0962.03039
[2] Ambos-Spies, K.; Mayordomo, E.; Wang, Y.; Zheng, X., Resource-bounded balanced genericity, stochasticity and weak randomness, (Puech, C.; Reischuk, R., Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science. Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science, STACS’96, Grenoble, France. Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science. Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science, STACS’96, Grenoble, France, Lecture Notes in Computer Science, vol. 1046 (1996), Springer-Verlag: Springer-Verlag Berlin), 63-74 · Zbl 1379.68185
[3] Ambos-Spies, K.; Merkle, W.; Reimann, J.; Stephan, F., Hausdorff dimension in exponential time, (Proceedings of the 16th Annual IEEE Conference on Computational Complexity (2000), IEEE Computer Society, IEEE Computer Society Press: IEEE Computer Society, IEEE Computer Society Press Chicago, IL, USA), 210-217
[4] Buhrman, H.; van Melkebeek, D.; Regan, K. W.; Sivakumar, D.; Strauss, M., A generalization of resource-bounded measure, with application to the BPP vs. EXP problem, SIAM J. Comput., 30, 2, 576-601 (2000) · Zbl 0963.68230
[5] Cai, J.-Y.; Hartmanis, J., On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line, J. Comput. System Sci., 49, 3, 605-619 (1994) · Zbl 0824.68054
[6] Calude, C. S., A characterization of c.e. random reals, Theoret. Comput. Sci., 271, 3-14 (2002) · Zbl 0992.68080
[7] R. Downey, D. Hirschfeldt, A. Nies, S. Terwijn, Calibrating randomness. Bull. Symbolic Logic (in press); R. Downey, D. Hirschfeldt, A. Nies, S. Terwijn, Calibrating randomness. Bull. Symbolic Logic (in press) · Zbl 1113.03037
[8] Kolmogorov, A. N., On tables of random numbers, Sankhyā, Ser. A, 25, 369-376 (1963), (Reprinted as [9]) · Zbl 0126.33203
[9] Kolmogorov, A. N., On tables of random numbers, Theoret. Comput. Sci., 207, 2, 387-395 (1998), (Reprint of [8]) · Zbl 0948.68125
[10] Lathrop, J. I.; Lutz, J. H., Recursive Computational Depth, Inform. and Comput., 153, 1, 139-172 (1999) · Zbl 1045.68569
[11] Li, M.; Vitányi, P., An Introduction to Kolmogorov Complexity and its Applications, (Graduate Texts in Computer Science (1997), Springer: Springer New York) · Zbl 1185.68369
[12] Loveland, D., A new interpretation of the von Mises’ concept of random sequence, Z. Math. Logik Grundlagen Math., 12, 279-294 (1966) · Zbl 0158.00601
[13] Lutz, J. H., Gales and the constructive dimension of individual sequences, (Automata, Languages and Programming. Automata, Languages and Programming, ICALP 2000, Geneva, Switzerland, 2000. Automata, Languages and Programming. Automata, Languages and Programming, ICALP 2000, Geneva, Switzerland, 2000, Lecture Notes in Comput. Sci., vol. 1853 (2000), Springer: Springer Berlin), 902-913 · Zbl 0973.68087
[14] Lutz, J. H.; Schweizer, D. L., Feasible reductions to Kolmogorov-Loveland stochastic sequences, Theoret. Comput. Sci., 225, 185-194 (1999) · Zbl 0930.68068
[15] Martin-Löf, P., The definition of random sequences, Inf. Control, 9, 602-619 (1966) · Zbl 0244.62008
[16] Mayordomo, E., A Kolmogorov complexity characterization of constructive Hausdorff dimension, Inform. Process. Lett., 84, 1, 1-3 (2002) · Zbl 1045.68570
[17] Merkle, W., The complexity of stochastic sequences, (Conference on Computational Complexity 2003 (2003), IEEE Computer Society, IEEE Computer Society Press: IEEE Computer Society, IEEE Computer Society Press Aarhus, Denmark), 230-235
[18] Merkle, W., The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences, J. Symbolic Logic, 68, 1362-1376 (2003) · Zbl 1065.03024
[19] J.S. Miller, L. Yu, On initial segment complexity and degrees of randomness (in preparation); J.S. Miller, L. Yu, On initial segment complexity and degrees of randomness (in preparation) · Zbl 1140.68028
[20] Muchnik, A. A.; Semenov, A. L.; Uspensky, V. A., Mathematical metaphysics of randomness, Theoret. Comput. Sci., 207, 2, 263-317 (1998) · Zbl 0922.60014
[21] Odifreddi, P., Classical Recursion Theory. The Theory of Functions and Sets of Natural Numbers, (Studies in Logic and the Foundations of Mathematics, vol. 125 (1989), North-Holland: North-Holland Amsterdam) · Zbl 0744.03044
[22] J. Reimann, Computability and fractal dimension, Doctoral Dissertation, Universität Heidelberg, 2004; J. Reimann, Computability and fractal dimension, Doctoral Dissertation, Universität Heidelberg, 2004 · Zbl 1080.03031
[23] Ryabko, B. Y., Coding of combinatorial sources and Hausdorff dimension, Dokl. Akad. Nauk SSSR, 277, 5, 1066-1070 (1984)
[24] Ryabko, B. Y., Noise-free coding of combinatorial sources, Hausdorff dimension and Kolmogorov complexity, Problemy Peredachi Informatsii, 22, 3, 16-26 (1986)
[25] B.Y. Ryabko, Private communication, April 2003; B.Y. Ryabko, Private communication, April 2003
[26] Schnorr, C. P., A unified approach to the definition of random sequences, Math. Systems Theory, 5, 246-258 (1971) · Zbl 0227.62005
[27] Schnorr, C. P., Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie (Randomness and Probability. An Algorithmic Foundation of Probability Theory), (Lecture Notes in Mathematics, vol. 218 (1971), Springer-Verlag: Springer-Verlag Berlin-Heidelberg-New York) · Zbl 0232.60001
[28] Shen’, A., On relations between different algorithmic definitions of randomness, Soviet Math. Dokl., 38, 316-319 (1989) · Zbl 0683.60002
[29] Staiger, L., Kolmogorov complexity and Hausdorff dimension, Inform. and Comput., 103, 2, 159-194 (1993) · Zbl 0789.68076
[30] Staiger, L., A tight upper bound on Kolmogorov complexity and uniformly optimal prediction, Theory Comput. Syst., 31, 3, 215-229 (1998) · Zbl 0896.68080
[31] Uspensky, V.; Semenov, A.; Shen’, A., Can an individual sequence of zeros and ones be random?, Russ. Math. Surv., 45, 1, 121-189 (1990) · Zbl 0702.03038
[32] M. van Lambalgen, Random sequences, Doctoral Dissertation, University of Amsterdam, 1987; M. van Lambalgen, Random sequences, Doctoral Dissertation, University of Amsterdam, 1987
[33] Zvonkin, A. K.; Levin, L. A., The complexity of finite objects and the basing of the concepts of information and randomness on the theory of algorithms, Uspehi Mat. Nauk, 25, 6(156), 85-127 (1970) · Zbl 0222.02027
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.