Effective packing dimension of -classes
Author: Chris J. Conidis
Journal: Proc. Amer. Math. Soc. 136 (2008), 3655-3662
MSC (2000): Primary 03Dxx, 68Qxx
Published electronically: May 15, 2008
MathSciNet review: 2415051
Full-text PDF Free Access
Abstract: We construct a -class 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 -classes.
- 1. 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, https://doi.org/10.1137/S0097539703446912
- 2. R. Downey and D.R. Hirschfeldt. Algorithmic Randomness and Complexity. Springer-Verlag, to appear.
- 3. Rod Downey, Denis R. Hirschfeldt, André Nies, and Sebastiaan A. Terwijn, Calibrating randomness, Bull. Symbolic Logic 12 (2006), no. 3, 411–491. MR 2248591
- 4. Kenneth Falconer, Fractal geometry, 2nd ed., John Wiley & Sons, Inc., Hoboken, NJ, 2003. Mathematical foundations and applications. MR 2118797
- 5. John M. Hitchcock, Correspondence principles for effective dimensions, Theory Comput. Syst. 38 (2005), no. 5, 559–571. MR 2156936, https://doi.org/10.1007/s00224-004-1122-1
- 6. 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
- 7. Jack H. Lutz, The dimensions of individual strings and sequences, Inform. and Comput. 187 (2003), no. 1, 49–79. MR 2018734, https://doi.org/10.1016/S0890-5401(03)00187-1
- 8. Joseph S. Miller and André Nies, Randomness and computability: open questions, Bull. Symbolic Logic 12 (2006), no. 3, 390–410. MR 2248590
- 9. A. Nies, Computability and Randomness. Oxford University Press, to appear.
- 10. 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
- 11. R. I. Soare, Computability Theory and Applications, Springer-Verlag, Heidelberg, to appear.
- K. B. Athreya, J. M. Hitchcock, J. H. Lutz, and E. Mayordomo. Effective strong dimension in algorithmic information and computational complexity. SIAM Journal on Computing, vol. 37 (2007) pp. 671-705. MR 2341912
- R. Downey and D.R. Hirschfeldt. Algorithmic Randomness and Complexity. Springer-Verlag, to appear.
- R. Downey, D.R. Hirschfeldt, A. Nies, and S.A. Terwijn. Calibrating randomness. The Bulletin of Symbolic Logic, vol. 12 (2006) pp. 411-491. MR 2248591 (2007j:03055)
- K. Falconer. Fractal Geometry: Mathematical Foundations and Applications. John Wiley & Sons, second edition, 2003. MR 2118797 (2006b:28001)
- J.M. Hitchcock. Correspondence principles for effective dimensions. Theory of Computing Systems, vol. 38 (2005) pp. 559-571. MR 2156936 (2007a:03049)
- M. Li and P.M.B. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Springer-Verlag, Berlin, second edition, 1997. MR 1438307 (97k:68086)
- J.H. Lutz. The dimensions of individual strings and sequences. Information and Computation, vol. 187 (2003), pp. 49-79. MR 2018734 (2005k:68099)
- J. Miller and A. Nies. Randomness and computability: Open questions. The Bulletin of Symbolic Logic, vol. 12 (2006), pp. 390-410. MR 2248590 (2007c:03059)
- A. Nies, Computability and Randomness. Oxford University Press, to appear.
- R. I. Soare, Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Springer-Verlag, Heidelberg, 1987. MR 882921 (88m:03003)
- R. I. Soare, Computability Theory and Applications, Springer-Verlag, Heidelberg, to appear.
Chris J. Conidis
Affiliation: Department of Mathematics, The University of Chicago, 5734 University Avenue, Chicago, Illinois 60637-1546
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
Article copyright: © Copyright 2008 American Mathematical Society