zbMATH — the first resource for mathematics

Turing degrees of reals of positive effective packing dimension. (English) Zbl 1191.68304
Summary: A relatively longstanding question in algorithmic randomness is Jan Reimann’s question whether there is a Turing cone of broken dimension. That is, is there a real \(A\) such that \(\{B: B \leqslant _T A\}\) contains no 1-random real, yet contains elements of nonzero effective Hausdorff dimension? We show that the answer is affirmative if Hausdorff dimension is replaced by its inner analogue packing dimension. We construct a minimal degree of effective packing dimension 1. This leads us to examine the Turing degrees of reals with positive effective packing dimension. Unlike effective Hausdorff dimension, this is a notion of complexity which is shared by both random and sufficiently generic reals. We provide a characterization of the c.e. array noncomputable degrees in terms of effective packing dimension.

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
03D28 Other Turing degree structures
03D32 Algorithmic randomness and dimension
Full Text: DOI
[1] Athreya, K.; Hitchcock, J.; Lutz, J.; Mayordomo, E., Effective strong dimension in algorithmic information and computational complexity, SIAM journal on computing, 37, 3, 671-705, (2007) · Zbl 1144.68029
[2] Barzdins, J., Complexity of programs to determine whether natural numbers not greater than n belong to a recursively enumerable set, Soviet mathematics doklady, 9, 1251-1254, (1968) · Zbl 0193.31601
[3] Bienvenu, L.; Doty, D.; Stephan, F., Constructive dimension and weak truth-table degrees. conference of computability in Europe 2007, ()
[4] C. Conidis, PhD Thesis, University of Chicago, in preparation
[5] de Leeuw, K.; Moore, E.F.; Shannon, C.E.; Shapiro, N., Computability by probabilistic machines, (), 183-212
[6] Doty, D., Dimension extractors and optimal decompression, () · Zbl 1166.68019
[7] R. Downey, D. Hirschfeldt, Algorithmic Randomness and Complexity, Springer-Verlag, in press · Zbl 1221.68005
[8] Downey, R.; Hirschfeldt, D.; Nies, A.; Terwijn, S., Calibrating randomness, Bulletin of symbolic logic, 3, 411-491, (2006) · Zbl 1113.03037
[9] Downey, R.; Jockusch, C.; Stob, M., Array nonrecursive sets and multiple permitting arguments, (), 141-174 · Zbl 0713.03020
[10] Downey, R.; Jockusch, C.; Stob, M., Array nonrecursive degrees and genericity, (), 93-105 · Zbl 0849.03029
[11] Falconer, K., Fractal geometry, mathematical foundations & applications, (1992), Wiley & Sons
[12] Y. Gabbay, Double jump inversions and strong minimal covers in the Turing degrees, PhD Thesis, Cornell University, 2004
[13] Hausdorff, F., Dimension und äußeres maß, Mathematische annalen, 79, 157-179, (1919) · JFM 46.0292.01
[14] Ishmukhametov, S., Weak recursive degrees and a problem of spector, (), 81-88 · Zbl 0951.03036
[15] Kummer, M., Kolmogorov complexity and instance complexity of recursively enumerable sets, SIAM journal of computing, 25, 1123-1143, (1996) · Zbl 0859.03015
[16] Lerman, M., Degrees of unsolvability. local and global theory, (), (xiii+307 pp.) · Zbl 0542.03023
[17] Li, M.; Vitányi, P., Kolmogorov complexity and its applications, (1993), Springer-Verlag
[18] Lutz, J., Category and measure in complexity classes, SIAM journal on computing, 19, 1100-1131, (1990) · Zbl 0711.68046
[19] Lutz, J., The dimensions of individual strings and sequences, Information and computation, 187, 49-79, (2003) · Zbl 1090.68053
[20] Mayordomo, E., A Kolmogorov complexity characterization of constructive Hausdorff dimension, Information processing letters, 84, 1-3, (2002) · Zbl 1045.68570
[21] Miller, J.S.; Nies, A., Randomness and computability: open questions, Bulletin symbolic logic, 12, 3, 390-410, (2006) · Zbl 1169.03033
[22] A. Nies, Computability and Randomness, Oxford University Press, in preparation
[23] A. Nies, J. Reimann, A lower cone in the wtt degrees of non-integral effective dimension, in: Proceedings of IMS Workshop on Computational Prospects of Infinity, Singapore, 2006 · Zbl 1158.03026
[24] J. Reimann, Computability and fractal dimension, Ph.D. thesis, Universität Heidelberg, 2004 · Zbl 1080.03031
[25] Sacks, G.E., Forcing with perfect closed sets, (), 331-355
[26] Soare, R., Recursively enumerable sets and degrees, (1987), Springer Berlin · Zbl 0623.03042
[27] Staiger, L., Kolmogorov complexity and Hausdorff dimension, Information and computation, 103, 159-194, (1993) · Zbl 0789.68076
[28] Terwijn, S.; Zambella, D., Algorithmic randomness and lowness, Journal of symbolic logic, 66, 1199-1205, (2001) · Zbl 0990.03033
[29] D. Zambella, On sequences with simple initial segments, ILLC technical report, ML-1990-05, University of Amsterdam, 1990
[30] M. Zimand, Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences, in: Proceedings CSR 2008, Moscow, June 2008 · Zbl 1143.68020
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.