zbMATH — the first resource for mathematics

Avoiding effective packing dimension 1 below array noncomputable c.e. degrees. (English) Zbl 1415.03047
The present article is concerned with the notion of effective packing dimension when applied to Turing lower cones. L. Bienvenu et al. [Theory Comput. Syst. 45, No. 4, 740–755 (2009; Zbl 1183.68281)] and L. Fortnow et al. [Lect. Notes Comput. Sci. 4051, 335–345 (2006; Zbl 1223.68060)] have independently shown that when taking the supremum over the effective packing dimensions of all sets in the Turing lower cone of a set \(X\), then that number must either be 0 or 1. This behaviour is notable as it is in stark contrast to that observed by J. S. Miller [Adv. Math. 226, No. 1, 373–384 (2011; Zbl 1214.03030)] for the closely related notion of effective Hausdorff dimension.
An obvious example for when the supremum takes the value 0 is if \(X\) is computable: then all sets in \(X\)’s lower cone are also computable, and all of them have effective packing dimension 0. For the value 1, there are two possible cases: The supremum might be an attained maximum over the lower cone; or it might be an unattained supremum. Clearly, lower cones of the first type exist: if \(X\) is Martin-Löf random, \(X\) has effective packing dimension 1. C. J. Conidis [J. Symb. Log. 77, No. 2, 447–474 (2012; Zbl 1251.03047)] showed that lower cones of the second type exist as well.
A natural question was then to ask which lower cones exactly are of the second type. The authors precisely answer this question for lower cones that are below the halting problem. A result of M. Kummer [SIAM J. Comput. 25, No. 6, 1123–1143 (1996; Zbl 0859.03015)] suggest that array noncomputability may have a role to play in this particular case. And indeed, within the c.e. sets, the present article characterizes the array noncomputable sets as exactly those below which a lower cone of the second type can be found.
The result is proved using pruned clumpy trees, building on the notion of clumpy trees introduced by R. Downey and N. Greenberg [Inf. Process. Lett. 108, No. 5, 298–303 (2008; Zbl 1191.68304)].

03D32 Algorithmic randomness and dimension
03D28 Other Turing degree structures
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
PDF BibTeX Cite
Full Text: DOI
[1] Athreya, K. B., Hitchcock, J. M., Lutz, J. H., and Mayordomo, E., Effective strong dimension in algorithmic information and computational complexity. SIAM Journal on Computing, vol. 37 (2007), no. 3, pp. 671-705. doi:10.1137/S0097539703446912 · Zbl 1144.68029
[2] Bienvenu, L., Doty, D., and Stephan, F., Constructive dimension and Turing degrees. Theory of Computing Systems, vol. 45 (2009), pp. 740-755. doi:10.1007/s00224-009-9170-1 · Zbl 1183.68281
[3] Conidis, C. J., A real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one, this Journal, vol. 77 (2012), pp. 447-474. · Zbl 1251.03047
[4] Day, A.
[5] Downey, R. G. and Hirschfeldt, D. R., Algorithmic Randomness and Complexity, Springer-Verlag, New York, 2010. · Zbl 1221.68005
[6] Downey, R. and Greenberg, N., Turing degrees of reals of positive effective packing dimension. Information Processing Letters, vol. 108 (2008), no. 5, pp. 298-303. doi:10.1016/j.ipl.2008.05.028 · Zbl 1191.68304
[7] Downey, R., Jockusch, C. G., and Stob, M., Array nonrecursive degrees and genericity, London Mathematical Society Lecture Notes Series 224 (Cooper, S. B., Slaman, T. A., and Wainer, S. S., editors), Cambridge University Press, Cambridge, 1996, pp. 93-105. · Zbl 0849.03029
[8] Downey, R. and Ng, K. M., Effective packing dimension and traceability. Notre Dame Journal of Formal Logic, vol. 51 (2010), no. 2, pp. 279-290. doi:10.1215/00294527-2010-017 · Zbl 1204.03042
[9] Fortnow, L., Hitchcock, J. M., Pavan, A., Vinodchandran, N. V., and Wang, F., Extracting Kolmogorov complexity with applications to dimension zero-one laws, Proceedings of the 33rd International Colloquium on Automata, Languages, and Programming (Bugliesi, M., Preneel, B., Sassone, V., and Wegener, I., editors), Springer-Verlag, Berlin, 2006, pp. 335-345. · Zbl 1223.68060
[10] Kummer, M., Kolmogorov complexity and instance complexity of recursively enumerable sets. SIAM Journal on Computing, vol. 25 (1996), no. 6, pp. 1123-1143. doi:10.1137/S0097539794268789 · Zbl 0859.03015
[11] Lutz, J. H., The dimensions of individual strings and sequences. Information and Computation, vol. 187 (2003), no. 1, pp. 49-79. doi:10.1016/S0890-5401(03)00187-1 · Zbl 1090.68053
[12] Lutz, J. H., Effective fractal dimensions. Mathematical Logic Quarterly, vol. 51 (2005), no. 1, pp. 62-72. doi:10.1002/malq.200310127 · Zbl 1058.03044
[13] Mayordomo, E., A Kolmogorov complexity characterization of constructive Hausdorff dimension. Information Processing Letters, vol. 84 (2002), no. 1, pp. 1-3. doi:10.1016/S0020-0190(02)00343-5 · Zbl 1045.68570
[14] Miller, J. S., Extracting information is hard: A Turing degreee of non-integral effective Hausdorff dimension. Advances in Mathematics, vol. 226 (2011), no. 1, pp. 373-384. doi:10.1016/j.aim.2010.06.024 · Zbl 1214.03030
[15] Simpson, S. G., Symbolic dynamics: Entropy = dimension = complexity. Theory of Computing Systems, vol. 56 (2015), no. 3, pp. 527-543. doi:10.1007/s00224-014-9546-8 · Zbl 1355.37023
[16] Soare, R. I., Recursively Enumerable Sets and Segrees, (1987), Springer-Verlag: Springer-Verlag, Berlin
[17] Staiger, L., Kolmogorov complexity and Hausdorff dimension. Information and Computation, vol. 103 (1993), no. 2, pp. 159-194. doi:10.1006/inco.1993.1017 · Zbl 0789.68076
[18] Stephenson, J. R., Controlling effective packing dimension of \({\rm{\Delta }}_2^0\) degrees. The Notre Dame Journal of Formal Logic, vol. 57 (2016), no. 1, pp. 73-93. doi:10.1215/00294527-3328401 · Zbl 1352.03048
[19] Sullivan, D., Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups. Acta Mathematica, vol. 153 (1984), no. 1, pp. 259-277. doi:10.1007/BF02392379 · Zbl 0566.58022
[20] Tricot, C., Two definitions of fractional dimension. Mathematical Proceedings of the Cambridge Philosophical Society, vol. 91 (1982), pp. 57-74. doi:10.1017/S0305004100059119 · Zbl 0483.28010
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.