Effective packing dimension of $\Pi ^0_1$-classes
HTML articles powered by AMS MathViewer
- by Chris J. Conidis PDF
- Proc. Amer. Math. Soc. 136 (2008), 3655-3662 Request permission
Abstract:
We construct a $\Pi ^0_1$-class $X$ that has classical packing dimension 0 and effective packing dimension 1. This implies that, unlike in the case of effective Hausdorff dimension, there is no natural correspondence principle (as defined by Lutz) for effective packing dimension. We also examine the relationship between upper box dimension and packing dimension for $\Pi ^0_1$-classes.References
- Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo, Effective strong dimension in algorithmic information and computational complexity, SIAM J. Comput. 37 (2007), no. 3, 671–705. MR 2341912, DOI 10.1137/S0097539703446912
- R. Downey and D.R. Hirschfeldt. Algorithmic Randomness and Complexity. Springer-Verlag, to appear.
- Rod Downey, Denis R. Hirschfeldt, André Nies, and Sebastiaan A. Terwijn, Calibrating randomness, Bull. Symbolic Logic 12 (2006), no. 3, 411–491. MR 2248591
- Kenneth Falconer, Fractal geometry, 2nd ed., John Wiley & Sons, Inc., Hoboken, NJ, 2003. Mathematical foundations and applications. MR 2118797, DOI 10.1002/0470013850
- John M. Hitchcock, Correspondence principles for effective dimensions, Theory Comput. Syst. 38 (2005), no. 5, 559–571. MR 2156936, DOI 10.1007/s00224-004-1122-1
- Ming Li and Paul Vitányi, An introduction to Kolmogorov complexity and its applications, 2nd ed., Graduate Texts in Computer Science, Springer-Verlag, New York, 1997. MR 1438307, DOI 10.1007/978-1-4757-2606-0
- Jack H. Lutz, The dimensions of individual strings and sequences, Inform. and Comput. 187 (2003), no. 1, 49–79. MR 2018734, DOI 10.1016/S0890-5401(03)00187-1
- Joseph S. Miller and André Nies, Randomness and computability: open questions, Bull. Symbolic Logic 12 (2006), no. 3, 390–410. MR 2248590
- A. Nies, Computability and Randomness. Oxford University Press, to appear.
- Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7
- R. I. Soare, Computability Theory and Applications, Springer-Verlag, Heidelberg, to appear.
Additional Information
- Chris J. Conidis
- Affiliation: Department of Mathematics, The University of Chicago, 5734 University Avenue, Chicago, Illinois 60637-1546
- Email: conidis@math.uchicago.edu
- Received by editor(s): August 2, 2007
- Received by editor(s) in revised form: August 22, 2007
- Published electronically: May 15, 2008
- Additional Notes: The author would like to acknowledge the helpful input he received from Jan Reimann, as well as his thesis advisors, Robert I. Soare and Denis R. Hirschfeldt. The author would also like to thank the American Institute of Mathematics for hosting a valuable workshop in effective randomness which lead to the publication of this article.
- Communicated by: Julia Knight
- © Copyright 2008 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 136 (2008), 3655-3662
- MSC (2000): Primary 03Dxx, 68Qxx
- DOI: https://doi.org/10.1090/S0002-9939-08-09335-0
- MathSciNet review: 2415051