# constructive dimension and turing degrees

- 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

- Iowa State University United States
- National University of Singapore Singapore
- Department of Computer Science Portland State University United States

- 1
- 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.

- 1
- 2