|
Effective packing dimension of  -classes
Author(s):
Chris
J.
Conidis
Journal:
Proc. Amer. Math. Soc.
136
(2008),
3655-3662.
MSC (2000):
Primary 03Dxx, 68Qxx
Posted:
May 15, 2008
Retrieve article in:
PDF
Abstract |
References |
Similar articles |
Additional information
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.
References:
-
- 1.
- 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
- 2.
- R. Downey and D.R. Hirschfeldt. Algorithmic Randomness and Complexity. Springer-Verlag, to appear.
- 3.
- 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)
- 4.
- K. Falconer. Fractal Geometry: Mathematical Foundations and Applications. John Wiley & Sons, second edition, 2003. MR 2118797 (2006b:28001)
- 5.
- J.M. Hitchcock. Correspondence principles for effective dimensions. Theory of Computing Systems, vol. 38 (2005) pp. 559-571. MR 2156936 (2007a:03049)
- 6.
- 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)
- 7.
- J.H. Lutz. The dimensions of individual strings and sequences. Information and Computation, vol. 187 (2003), pp. 49-79. MR 2018734 (2005k:68099)
- 8.
- 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)
- 9.
- A. Nies, Computability and Randomness. Oxford University Press, to appear.
- 10.
- 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)
- 11.
- R. I. Soare, Computability Theory and Applications, Springer-Verlag, Heidelberg, to appear.
Similar Articles:
Retrieve articles in Proceedings of the American Mathematical Society
with MSC
(2000):
03Dxx, 68Qxx
Retrieve articles in all Journals with MSC
(2000):
03Dxx, 68Qxx
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
DOI:
10.1090/S0002-9939-08-09335-0
PII:
S 0002-9939(08)09335-0
Received by editor(s):
August 2, 2007,
Received by editor(s) in revised form:
August 22, 2007
Posted:
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 of article:
Copyright
2008,
American Mathematical Society
|
Comments: webmaster@ams.org