×

zbMATH — the first resource for mathematics

The dimensions of individual strings and sequences. (English) Zbl 1090.68053
Summary: A constructive version of Hausdorff dimension is developed using constructive supergales, which are betting strategies that generalize the constructive supermartingales used in the theory of individual random sequences. This constructive dimension is used to assign every individual (infinite, binary) sequence \(S\) a dimension, which is a real number \(\text{dim}(S)\) in the interval \([0,1]\). Sequences that are random (in the sense of Martin-Löf) have dimension 1, while sequences that are decidable, \(\Sigma_1^0\), or \(\Pi_1^0\) have dimension 0. It is shown that for every \(\Delta^0_2\)-computable real number \(\alpha\) in \([0,1]\) there is a \(\Delta^0_2\) sequence \(S\) such that \(\dim(S)=\alpha\). A discrete version of constructive dimension is also developed using termgales, which are supergale-like functions that bet on the terminations of (finite, binary) strings as well as on their successive bits. This discrete dimension is used to assign each individual string \(w\) a dimension, which is a nonnegative real number \(\text{dim}(w)\). The dimension of a sequence is shown to be the limit inferior of the dimensions of its prefixes. The Kolmogorov complexity of a string is proven to be the product of its length and its dimension. This gives a new characterization of algorithmic information and a new proof of Mayordomo’s recent theorem stating that the dimension of a sequence is the limit inferior of the average Kolmogorov complexity of its first \(n\) bits. Every sequence that is random relative to any computable sequence of coin-toss biases that converge to a real number \(\beta\) in \((0,1)\) is shown to have dimension \(\mathcal H(\beta)\), the binary entropy of \(\beta\).

MSC:
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Besicovitch, A.S., On the sum of digits of real numbers represented in the dyadic system, Math. annal., 110, 321-330, (1934) · Zbl 0009.39503
[2] Billingsley, P., Ergodic theory and information, (1965), Wiley New York · Zbl 0141.16702
[3] Cai, J.; Hartmanis, J., On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line, J. comput. syst. sci., 49, 605-619, (1994) · Zbl 0824.68054
[4] Chaitin, G.J., On the length of programs for computing finite binary sequences, J. assoc. comput. Mach., 13, 547-569, (1966) · Zbl 0158.25301
[5] Chaitin, G.J., On the length of programs for computing finite binary sequences: statistical considerations, J. assoc. comput. Mach., 16, 145-159, (1969) · Zbl 0187.28303
[6] Chaitin, G.J., A theory of program size formally identical to information theory, J. assoc. comput. Mach., 22, 329-340, (1975) · Zbl 0309.68045
[7] Chaitin, G.J., Incompleteness theorems for random reals, Adv. appl. math., 8, 119-146, (1987) · Zbl 0649.03046
[8] Cover, T.M.; Thomas, J.A., Elements of information theory, (1991), Wiley New York · Zbl 0762.94001
[9] Eggleston, H.G., The fractional dimension of a set defined by decimal properties, Quart. J. math., Oxford ser., 20, 31-36, (1949) · Zbl 0031.20801
[10] Falconer, K., The geometry of fractal sets, (1985), Cambridge University Press Cambridge · Zbl 0587.28004
[11] Falconer, K., Fractal geometry: mathematical foundations and applications, (1990), Wiley New York · Zbl 0689.28003
[12] S.A. Fenner, Gales and supergales are equivalent for defining constructive Hausdorff dimension, Technical Report cs.CC/0208044, ACM Computing Research Repository, 2002
[13] Good, I.J., The fractional dimensional theory of continued fractions, Proc. Cambridge philos. soc., 37, 199-228, (1941) · Zbl 0061.09408
[14] Hausdorff, F., Dimension und äusseres mass, Math. annal., 79, 157-179, (1919) · JFM 46.0292.01
[15] Hitchcock, J.M., Gales suffice for constructive dimension, Inf. process. lett., 86, 9-12, (2003) · Zbl 1162.68462
[16] J.M. Hitchcock, Correspondence principles for effective dimensions, in: Proceedings of the 29th International Colloquium on Automata, Languages, and Programming, 2002, pp. 561-571 · Zbl 1057.68038
[17] Kakutani, S., On the equivalence of infinite product measures, Ann. math., 49, 214-224, (1948) · Zbl 0030.02303
[18] Kolmogorov, A.N., On tables of random numbers, Sankhyā, ser. A, 25, 369-376, (1963) · Zbl 0126.33203
[19] Kolmogorov, A.N., Three approaches to the quantitative definition of ‘information’, Probl. inf. transm., 1, 1-7, (1965) · Zbl 0271.94018
[20] Kolmogorov, A.N., Combinatorial foundations of information theory and calculus of probabilities, Russ. math. surveys, 38, 29-40, (1983) · Zbl 0597.60002
[21] Kreisel, G., Note on arithmetical models for consistent formulae of the predicate calculus, Fundamen. math., 37, 265-285, (1950) · Zbl 0040.00302
[22] Levin, L.A., On the notion of a random sequence, Sov. math. dokl., 14, 1413-1416, (1973) · Zbl 0312.94006
[23] Levin, L.A., Laws of information conservation (nongrowth) and aspects of the foundation of probability theory, Probl. inf. transm., 10, 206-210, (1974)
[24] Li, M.; Vitányi, P.M.B., An introduction to Kolmogorov complexity and its applications, (1997), Springer Berlin
[25] Loveland, D.W., The Kleene hierarchy classification of recursively random sequences, Trans. am. math. soc., 125, 497-510, (1966) · Zbl 0189.01101
[26] Loveland, D.W., A new interpretation of von mises’ concept of a random sequence, Z. math. logik, 12, 279-294, (1966) · Zbl 0158.00601
[27] Lutz, J.H., Dimension in complexity classes, SIAM J. comput., 32, 1236-1259, (2003) · Zbl 1026.68059
[28] Lutz, J.H., Gales and the constructive dimension of individual sequences, (), 902-913 · Zbl 0973.68087
[29] Martin-Löf, P., The definition of random sequences, Inf. contr., 9, 602-619, (1966) · Zbl 0244.62008
[30] Martin-Löf, P., Complexity oscillations in infinite binary sequences, Z. wahrscheinlichkeit., 19, 225-230, (1971) · Zbl 0212.23103
[31] Mayordomo, E., A Kolmogorov complexity characterization of constructive Hausdorff dimension, Inf. process. lett., 84, 1-3, (2002) · Zbl 1045.68570
[32] Moschovakis, Y.N., Descriptive set theory, (1980), North-Holland Amsterdam · Zbl 0433.03025
[33] Odifreddi, P., Classical recursion theory, (1989), Elsevier Amsterdam · Zbl 0931.03057
[34] Rogers, H., Theory of recursive functions and effective computability, (1967), McGraw-Hill New York · Zbl 0183.01401
[35] Ryabko, B.Ya., Coding of combinatorial sources and Hausdorff dimension, Sov. math. dokl., 30, 219-222, (1984) · Zbl 0581.94007
[36] Ryabko, B.Ya., Noiseless coding of combinatorial sources, Probl. inf. transm., 22, 170-179, (1986) · Zbl 0613.94006
[37] Ryabko, B.Ya., Algorithmic approach to the prediction problem, Probl. inf. transm., 29, 186-193, (1993) · Zbl 0800.68502
[38] Ryabko, B.Ya., The complexity and effectiveness of prediction problems, J. complexity, 10, 281-295, (1994) · Zbl 0812.68082
[39] Schnorr, C.P., A unified approach to the definition of random sequences, Math. syst. theory, 5, 246-258, (1971) · Zbl 0227.62005
[40] Schnorr, C.P., Zufälligkeit und wahrscheinlichkeit, Lect. notes math., 218, (1971)
[41] Schnorr, C.P., Process complexity and effective random tests, J. comput. syst. sci., 7, 376-388, (1973) · Zbl 0273.68036
[42] Schnorr, C.P., A survey of the theory of random sequences, (), 193-210
[43] Shen’, A.Kh., The frequency approach to the definition of a random sequence, Semiotika informatika, 18, 14-42, (1982), (in Russian)
[44] Shen’, A.Kh., On relations between different algorithmic definitions of randomness, Sov. math. dokl., 38, 316-319, (1989) · Zbl 0683.60002
[45] Soare, R.I., Recursively enumerable sets and degrees, (1987), Springer Berlin · Zbl 0667.03030
[46] Solomonoff, R.J., A formal theory of inductive inference, Inf. contr., 7, 1-22, (1964), 224-254 · Zbl 0258.68045
[47] R.M. Solovay, 1975, Reported in [7]
[48] Staiger, L., Kolmogorov complexity and Hausdorff dimension, Inf. comput., 102, 159-194, (1993) · Zbl 0789.68076
[49] Staiger, L., A tight upper bound on Kolmogorov complexity and uniformly optimal prediction, Theory comput. syst., 31, 215-229, (1998) · Zbl 0896.68080
[50] Staiger, L., How much can you win when your adversary is handicapped?, Numbers, information and complexity, (2000), Kluwer Academic Publishers Dordrecht, pp. 403-412 · Zbl 0955.68058
[51] S.A. Terwijn, Personal communication, 2000
[52] M. van Lambalgen, Random sequences, Ph.D. Thesis, Department of Mathematics, University of Amsterdam, 1987 · Zbl 0628.60001
[53] van Lambalgen, M., Von mises’ definition of random sequences reconsidered, J. symbolic logic, 52, 725-755, (1987) · Zbl 0628.60001
[54] Vovk, V.G., On a randomness criterion, Sov. math. dokl., 35, 656-660, (1987) · Zbl 0646.60003
[55] 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. surveys, 25, 83-124, (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. 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.