Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-20T08:27:04.475Z Has data issue: false hasContentIssue false
  • English
  • Français

AVOIDING EFFECTIVE PACKING DIMENSION 1 BELOW ARRAY NONCOMPUTABLE C.E. DEGREES

Published online by Cambridge University Press:  01 August 2018

ROD DOWNEY  and
JONATHAN STEPHENSON
ROD DOWNEY
Affiliation:
DEPARTMENT OF MATHEMATICS, STATISTICS, AND OPERATIONS RESEARCH VICTORIA UNIVERSITY OF WELLINGTON P.O. BOX 600 WELLINGTON, NEW ZEALANDE-mail:[email protected]
JONATHAN STEPHENSON
Affiliation:
MATHEMATICS AND STATISTICS VALPARAISO UNIVERSITY GELLERSEN CENTER, ROOM 112 1900 CHAPEL DRIVE VALPARAISO, IN46383, USAE-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Recent work of Conidis [3] shows that there is a Turing degree with nonzero effective packing dimension, but which does not contain any set of effective packing dimension 1.

This article shows the existence of such a degree below every c.e. array noncomputable degree, and hence that they occur below precisely those of the c.e. degrees which are array noncomputable.

Keywords

03D3268Q30Kolmogorov complexityeffective packing dimensionarray noncomputability
Type
Articles
Information
The Journal of Symbolic Logic , Volume 83 , Issue 2 , June 2018 , pp. 717 - 739
Copyright
Copyright © The Association for Symbolic Logic 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

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.CrossRefGoogle Scholar
Bienvenu, L., Doty, D., and Stephan, F., Constructive dimension and Turing degrees. Theory of Computing Systems, vol. 45 (2009), pp. 740–755.CrossRefGoogle Scholar
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.Google Scholar
Day, A., A new proof of the Kolmogorov-Sinai theorem, in preparation.Google Scholar
Downey, R. G. and Hirschfeldt, D. R., Algorithmic Randomness and Complexity, Springer-Verlag, New York, 2010.CrossRefGoogle Scholar
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.CrossRefGoogle Scholar
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.Google Scholar
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.CrossRefGoogle Scholar
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.CrossRefGoogle Scholar
Kummer, M., Kolmogorov complexity and instance complexity of recursively enumerable sets. SIAM Journal on Computing, vol. 25 (1996), no. 6, pp. 1123–1143.CrossRefGoogle Scholar
Lutz, J. H., The dimensions of individual strings and sequences. Information and Computation, vol. 187 (2003), no. 1, pp. 49–79.CrossRefGoogle Scholar
Lutz, J. H., Effective fractal dimensions. Mathematical Logic Quarterly, vol. 51 (2005), no. 1, pp. 62–72.CrossRefGoogle Scholar
Mayordomo, E., A Kolmogorov complexity characterization of constructive Hausdorff dimension. Information Processing Letters, vol. 84 (2002), no. 1, pp. 1–3.CrossRefGoogle Scholar
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.CrossRefGoogle Scholar
Simpson, S. G., Symbolic dynamics: Entropy = dimension = complexity. Theory of Computing Systems, vol. 56 (2015), no. 3, pp. 527–543.CrossRefGoogle Scholar
Soare, R. I., Recursively Enumerable Sets and Segrees, Springer-Verlag, Berlin, 1987.CrossRefGoogle Scholar
Staiger, L., Kolmogorov complexity and Hausdorff dimension. Information and Computation, vol. 103 (1993), no. 2, pp. 159–194.CrossRefGoogle Scholar
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.CrossRefGoogle Scholar
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.CrossRefGoogle Scholar
Tricot, C., Two definitions of fractional dimension. Mathematical Proceedings of the Cambridge Philosophical Society, vol. 91 (1982), pp. 57–74.CrossRefGoogle Scholar