zbMATH — the first resource for mathematics

Constructive dimension and Turing degrees. (English) Zbl 1183.68281
Summary: This paper examines the constructive Hausdorff and packing dimensions of Turing degrees. The main result is that every infinite sequence \(S\) with constructive Hausdorff dimension \(\dim_{H}(S)\) and constructive packing dimension \(\dim_{P}(S)\) is Turing equivalent to a sequence \(R\) with \(\dim_{H}(R)\geq (\dim_{H}(S)/\dim_{P}(S)) - \epsilon \), for arbitrary \(\epsilon >0\). Furthermore, if \(\dim_{P}(S)>0\), then \(\dim_{P}(R)\geq 1 - \epsilon \). The reduction thus serves as a randomness extractor that increases the algorithmic randomness of \(S\), as measured by constructive dimension.
A number of applications of this result shed new light on the constructive dimensions of Turing degrees. A lower bound of \(\dim_{H}(S)/\dim_{P}(S)\) is shown to hold for the Turing degree of any sequence \(S\). A new proof is given of a previously-known zero-one law for the constructive packing dimension of Turing degrees. It is also shown that, for any regular sequence \(S\) (that is, \(\dim_{H}(S)=\dim_{P}(S)\)) such that \(\dim_{H}(S)>0\), the Turing degree of \(S\) has constructive Hausdorff and packing dimension equal to 1.
Finally, it is shown that no single Turing reduction can be a universal constructive Hausdorff dimension extractor, and that bounded Turing reductions cannot extract constructive Hausdorff dimension. We also exhibit sequences on which weak truth-table and bounded Turing reductions differ in their ability to extract dimension.
Reviewer: Reviewer (Berlin)

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI arXiv
[1] Athreya, K., Hitchcock, J., Lutz, J.H., Mayordomo, E.: Effective strong dimension, algorithmic information and computational complexity. SIAM J. Comput. 37, 671–705 (2007) · Zbl 1144.68029 · doi:10.1137/S0097539703446912
[2] Bienvenu, L., Doty, D., Stephan, F.: Constructive dimension and weak truth-table degrees. In: Cooper, S.B., Löwe, B., Sorbi, A. (eds.) Computation and Logic in the Real World–Third Conference of Computability in Europe (CiE 2007), Siena, Italy, June 18–23, 2007, Proceedings. Lecture Notes in Computer Science, vol. 4497, pp. 63–72. Springer, Berlin (2007) · Zbl 1151.03333
[3] Calude, C.S., Chaitin, G.J.: Randomness everywhere. Nature 400, 319–320 (1999) · doi:10.1038/22435
[4] Doty, D.: Every sequence is decompressible from a random one. In: Logical Approaches to Computational Barriers, Proceedings of the Second Conference on Computability in Europe, Swansea, UK, July 2006. Lecture Notes in Computer Science, vol. 3988, pp. 153–162. Springer, Berlin (2006) · Zbl 1145.03325
[5] Doty, D.: Dimension extractors and optimal decompression. Theory Comput. Syst. 43(3), 425–463 (2008). Special issue of invited papers from Computability in Europe 2006 · Zbl 1166.68019 · doi:10.1007/s00224-007-9024-7
[6] Fortnow, L., Hitchcock, J.M., Aduri, P., Vinodchandran, N.V., Wang, F.: Extracting Kolmogorov complexity with applications to dimension zero-one laws. In: Proceedings of the 33rd International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 4051, pp. 335–345. Springer, Berlin (2006) · Zbl 1223.68060
[7] Friedberg, R., Rogers, H.: Reducibilities and completeness for sets of integers. Z. Math. Log. Grundl. Math. 5, 117–125 (1959) · Zbl 0108.00602 · doi:10.1002/malq.19590050703
[8] Hausdorff, F.: Dimension und äusseres Mass. Math. Ann. 79, 157–179 (1919) · JFM 46.0292.01 · doi:10.1007/BF01457179
[9] Hemaspaandra, L., Hempel, H., Vogel, J.: Optimal separations for parallel versus sequential self-checking: parallelism can exponentially increase self-checking cost. Technical Report TR 691, Department of Computer Science, University of Rochester, May 1998
[10] Li, M., Vitányi, P.M.B.: An Introduction to Kolmogorov Complexity and its Applications, 2nd edn. Springer, Berlin (1997) · Zbl 0866.68051
[11] Lutz, J.H.: Dimension in complexity classes. SIAM J. Comput. 32, 1236–1259 (2003) · Zbl 1026.68059 · doi:10.1137/S0097539701417723
[12] Lutz, J.H.: The dimensions of individual strings and sequences. Inf. Comput. 187, 49–79 (2003) · Zbl 1090.68053 · doi:10.1016/S0890-5401(03)00187-1
[13] Lutz, J.H.: Effective fractal dimensions. Math. Log. Q. 51, 62–72 (2005). (Invited lecture at the International Conference on Computability and Complexity in Analysis, Cincinnati, OH, August 28–30, 2003) · Zbl 1058.03044 · doi:10.1002/malq.200310127
[14] Mayordomo, E.: A Kolmogorov complexity characterization of constructive Hausdorff dimension. Inf. Process. Lett. 84(1), 1–3 (2002) · Zbl 1045.68570 · doi:10.1016/S0020-0190(02)00343-5
[15] Miller, J.: Extracting information is hard. Technical Report (2008). http://www.math.uconn.edu/\(\sim\)josephmiller/Papers/dimension.pdf
[16] Nies, A., Reimann, J.: A lower cone in the wtt degrees of non-integral effective dimension. In: Proceedings of IMS workshop on Computational Prospects of Infinity, Singapore (2009, to appear). Earlier version appeared as Technical Report 63, Workgroup Mathematical Logic and Theoretical Computer Science, University of Heidelberg (2005)
[17] Odifreddi, P.: Classical Recursion Theory. Studies in Logic and the Foundations of Mathematics, vol. 125. North-Holland, Amsterdam (1989) · Zbl 0661.03029
[18] Post, E.L.: Recursively enumerable sets of positive integers and their decision problems. Bull. Am. Math. Soc. 50, 284–316 (1944) · Zbl 0063.06328 · doi:10.1090/S0002-9904-1944-08111-1
[19] Reimann, J.: Computability and fractal dimension. Doctoral thesis, Heidelberg (2005) · Zbl 1080.03031
[20] Reimann, J., Slaman, T.: Randomness, Entropy and Reducibility. Manuscript (2005)
[21] Ryabko, B.Ya.: Coding of combinatorial sources and Hausdorff dimension. Sov. Math. Dokl. 30, 219–222 (1984) · Zbl 0581.94007
[22] Ryabko, B.Ya.: Noiseless coding of combinatorial sources. Probl. Inf. Transm. 22, 170–179 (1986) · Zbl 0613.94006
[23] Shaltiel, R.: Recent developments in explicit constructions of extractors. Bull. EATCS 77, 67–95 (2002) · Zbl 1051.68070
[24] Soare, R.I.: Recursively Enumerable Sets and Degrees. Springer, Berlin (1987) · Zbl 0667.03030
[25] Stephan, F.: Hausdorff-dimension and weak truth-table reducibility. Technical Report TR52/05, School of Computing, National University of Singapore (2005) · Zbl 1138.03035
[26] Sullivan, D.: Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups. Acta Math. 153, 259–277 (1984) · Zbl 0566.58022 · doi:10.1007/BF02392379
[27] Tricot, C.: Two definitions of fractional dimension. Math. Proc. Camb. Philos. Soc. 91, 57–74 (1982) · Zbl 0483.28010 · doi:10.1017/S0305004100059119
[28] Turing, A.M.: Systems of logic based on ordinals. Proc. Lond. Math. Soc. 45, 161–228 (1939) · Zbl 0021.09704 · doi:10.1112/plms/s2-45.1.161
[29] Zimand, M.: Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences. Technical Report 0705.4658, Computing Research Repository (2007) · 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.