×

zbMATH — the first resource for mathematics

Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension. (English) Zbl 1214.03030
The major result in the paper under review is that there is a \(\Delta^0_2\) real with effective Hausdorff dimension \(\frac{1}{2}\) that does not compute a real of higher dimension.
Reviewer: Liang Yu (Nanjing)

MSC:
03D32 Algorithmic randomness and dimension
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Athreya, Krishna B.; Hitchcock, John M.; Lutz, Jack H.; Mayordomo, Elvira, Effective strong dimension in algorithmic information and computational complexity, (), 632-643 · Zbl 1122.68068
[2] Bienvenu, Laurent; Doty, David; Stephan, Frank, Constructive dimension and Turing degrees, Theory comput. syst., 45, 4, 740-755, (2009) · Zbl 1183.68281
[3] Chaitin, Gregory J., A theory of program size formally identical to information theory, J. assoc. comput. Mach., 22, 329-340, (1975) · Zbl 0309.68045
[4] R. Downey, D. Hirschfeldt, Algorithmic Randomness and Complexity, Springer-Verlag, Berlin, in press. · Zbl 1221.68005
[5] Downey, Rod; Greenberg, Noam, Turing degrees of reals of positive effective packing dimension, Inform. process. lett., 108, 5, 298-303, (2008) · Zbl 1191.68304
[6] Downey, Rod; Hirschfeldt, Denis R.; Nies, André; Terwijn, Sebastiaan A., Calibrating randomness, Bull. symbolic logic, 12, 3, 411-491, (2006) · Zbl 1113.03037
[7] Fortnow, Lance; Hitchcock, John M.; Pavan, A.; Vinodchandran, N.V.; Wang, Fengming, Extracting Kolmogorov complexity with applications to dimension zero-one laws, (), 335-345 · Zbl 1223.68060
[8] Noam Greenberg, Joseph S. Miller, Diagonally non-recursive functions and effective Hausdorff dimension, Bull. London Math. Soc., in press. · Zbl 1225.03055
[9] Kjos-Hanssen, Bjørn; Merkle, Wolfgang; Stephan, Frank, Kolmogorov complexity and the recursion theorem, (), 149-161 · Zbl 1137.03026
[10] Levin, L.A., Laws of information conservation (non-growth) and aspects of the foundation of probability theory, Probl. inf. transm., 10, 3, 206-210, (1974)
[11] Li, M.; Vitányi, P., An introduction to Kolmogorov complexity and its applications, Texts monogr. comput. sci., (1993), Springer-Verlag New York · Zbl 0805.68063
[12] Lutz, Jack H., Gales and the constructive dimension of individual sequences, (), 902-913 · Zbl 0973.68087
[13] Lutz, Jack H., Effective fractal dimensions, Math. log. Q., 51, 1, 62-72, (2005) · Zbl 1058.03044
[14] Martin-Löf, Per, The definition of random sequences, Inform. control, 9, 602-619, (1966) · Zbl 0244.62008
[15] Mayordomo, Elvira, A Kolmogorov complexity characterization of constructive Hausdorff dimension, Inform. process. lett., 84, 1, 1-3, (2002) · Zbl 1045.68570
[16] Miller, Joseph S.; Nies, André, Randomness and computability: open questions, Bull. symbolic logic, 12, 3, 390-410, (2006) · Zbl 1169.03033
[17] Nies, André, Computability and randomness, Oxford logic guides, vol. 51, (2009), Oxford University Press Oxford · Zbl 1169.03034
[18] Nies, André; Reimann, Jan, A lower cone in the wtt degrees of non-integral effective dimension, (), 249-260 · Zbl 1158.03026
[19] J. Reimann, Computability and fractal dimension, Doctoral dissertation, Universität Heidelberg, 2004, available at http://math.uni-heidelberg.de/logic/reimann/publications/phdthesis.pdf. · Zbl 1080.03031
[20] Reimann, Jan, Effectively closed sets of measures and randomness, Ann. pure appl. logic, 156, 1, 170-182, (2008) · Zbl 1153.03021
[21] Ryabko, B.Ya., Coding of combinatorial sources and Hausdorff dimension, Dokl. akad. nauk SSSR, 277, 5, 1066-1070, (1984) · Zbl 0581.94007
[22] Sántha, Miklós; Vazirani, Umesh V., Generating quasirandom sequences from semirandom sources, Twenty-fifth annual symposium on foundations of computer science, Singer Island, Fla., 1984, J. comput. system sci., 33, 1, 75-87, (1986) · Zbl 0612.94004
[23] Shaltiel, Ronen, Recent developments in extractors, () · Zbl 1082.68124
[24] Vazirani, Umesh V., Strong communication complexity or generating quasirandom sequences from two communicating semirandom sources, Combinatorica, 7, 4, 375-392, (1987) · Zbl 0643.94002
[25] Vereshchagin, Nikolai K.; Vyugin, Michael V., Independent minimum length programs to translate between given strings, Theoret. comput. sci., 271, 1-2, 131-143, (2002), Kolmogorov complexity · Zbl 0992.68083
[26] von Neumann, John, Various techniques for use in connection with random digits, (), 768-770
[27] Zimand, Marius, Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences, corr, (2007), Informal publication · Zbl 1143.68020
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.