publication . Article . Preprint . 2007

constructive dimension and turing degrees

Bienvenu, Laurent; Doty, David; Stephan, Frank;
Open Access
  • Published: 14 Jan 2007 Journal: Theory of Computing Systems, volume 45, pages 740-755 (issn: 1432-4350, eissn: 1433-0490, Copyright policy)
  • Publisher: Springer Science and Business Media LLC
Abstract
This paper examines the constructive Hausdorff and packing dimensions of Turing degrees. The main result is that every infinite sequence S with constructive Hausdorff dimension dim_H(S) and constructive packing dimension dim_P(S) is Turing equivalent to a sequence R with dim_H(R) <= (dim_H(S) / dim_P(S)) - epsilon, for arbitrary epsilon > 0. Furthermore, if dim_P(S) > 0, then dim_P(R) >= 1 - epsilon. The reduction thus serves as a *randomness extractor* that increases the algorithmic randomness of S, as measured by constructive dimension. A number of applications of this result shed new light on the constructive dimensions of Turing degrees. A lower bound of dim...
Subjects
arXiv: Mathematics::General TopologyMathematics::Metric GeometryComputer Science::Computational Complexity
free text keywords: Theoretical Computer Science, Computational Theory and Mathematics, Discrete mathematics, Description number, Time hierarchy theorem, Mathematics, Turing reduction, Combinatorics, Probabilistic Turing machine, symbols.namesake, symbols, Post's theorem, Hyperarithmetical theory, Packing dimension, Hausdorff dimension, Computer Science - Computational Complexity, Computer Science - Information Theory
29 references, page 1 of 2

[1] Krishna Athreya, John Hitchcock, Jack H. Lutz and Elvira Mayordomo. Effective strong dimension, algorithmic information and computational complexity. SIAM Journal on Computing, 37:671-705, 2007.

[2] Laurent Bienvenu, David Doty, and Frank Stephan. Constructive Dimension and Weak Truth-Table Degrees. in S. Barry Cooper, Benedikt Lo¨we, and Andrea Sorbi (editors), Computation and Logic in the Real World - Third Conference of Computability in Europe (CiE 2007), (Siena, Italy, June 18-23, 2007), Proceedings, Lecture Notes in Computer Science, volume 4497, Spring-Verlag, 2007, pp. 63-72.

[3] Cristian S. Calude and Gregory J. Chaitin. Randomness everywhere. Nature, 400:319- 320, 1999.

[4] David Doty. Every sequence is decompressible from a random one. In Logical Approaches to Computational Barriers, Proceedings of the Second Conference on Computability in Europe, Springer Lecture Notes in Computer Science, volume 3988 of Computability in Europe, Swansea, UK, July 2006, pp. 153-162.

[5] David Doty. Dimension extractors and optimal decompression. Theory of Computing Systems, 43(3-4):425-463, 2008. Special issue of selected papers from Computability in Europe 2006.

[6] Lance Fortnow, John M. Hitchcock, Pavan Aduri, N. Variyam Vinodchandran and Fengming Wang. Extracting Kolmogorov complexity with applications to dimension zero-one laws. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, Springer LNCS, 4051:335-345, 2006.

[7] Richard Friedberg and Hartley Rogers. Reducibilities and completeness for sets of integers. Zeitschrift fu¨r Mathematische Logik und Grundlagen der Mathematik, 5:117-125, 1959.

[8] Felix Hausdorff. Dimension und ¨ausseres Mass. Mathematische Annalen, 79:157-179, 1919.

[9] Lane Hemaspaandra, Harald Hempel and J¨org Vogel. Optimal Separations for Parallel versus Sequential Self-Checking: Parallelism Can Exponentially Increase Self-Checking Cost. Technical Report TR 691, Department of Computer Science, University of Rochester, May 1998.

[10] Ming Li and Paul M. B. Vit´anyi. An Introduction to Kolmogorov Complexity and its Applications. Springer-Verlag, Berlin, 1997. Second Edition.

[11] Jack H. Lutz. Dimension in complexity classes. SIAM Journal on Computing, 32:1236- 1259, 2003.

[12] Jack H. Lutz. The dimensions of individual strings and sequences. Information and Computation, 187:49-79, 2003.

[13] Jack H. Lutz. Effective fractal dimensions (invited lecture at the International Conference on Computability and Complexity in Analysis, Cincinnati, OH, August 28-30, 2003), Mathematical Logic Quarterly 51, pp. 62-72, 2005.

[14] Elvira Mayordomo. A Kolmogorov complexity characterization of constructive Hausdorff dimension. Information Processing Letters, 84(1):1-3, 2002.

[15] Joseph Miller. Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension. To appear in Advances in Mathematics.

29 references, page 1 of 2
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue