Kolmogorov complexity and the Recursion Theorem
HTML articles powered by AMS MathViewer
- by Bjørn Kjos-Hanssen, Wolfgang Merkle and Frank Stephan PDF
- Trans. Amer. Math. Soc. 363 (2011), 5465-5480 Request permission
Abstract:
Several classes of diagonally nonrecursive (DNR) functions are characterized in terms of Kolmogorov complexity. In particular, a set of natural numbers $A$ can wtt-compute a DNR function iff there is a nontrivial recursive lower bound on the Kolmogorov complexity of the initial segments of $A$. Furthermore, $A$ can Turing compute a DNR function iff there is a nontrivial $A$-recursive lower bound on the Kolmogorov complexity of the initial segments of $A$. $A$ is PA-complete, that is, $A$ can compute a $\{0,1\}$-valued DNR function, iff $A$ can compute a function $F$ such that $F(n)$ is a string of length $n$ and maximal $C$-complexity among the strings of length $n$. $A \geq _T K$ iff $A$ can compute a function $F$ such that $F(n)$ is a string of length $n$ and maximal $H$-complexity among the strings of length $n$. Further characterizations for these classes are given. The existence of a DNR function in a Turing degree is equivalent to the failure of the Recursion Theorem for this degree; thus the provided results characterize those Turing degrees in terms of Kolmogorov complexity which no longer permit the usage of the Recursion Theorem.References
- Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp, and Theodore A. Slaman, Comparing DNR and WWKL, J. Symbolic Logic 69 (2004), no. 4, 1089–1104. MR 2135656, DOI 10.2178/jsl/1102022212
- Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpre, Andrej Muchnik, Frank Stephan, and Leen Torenvliet, Enumerations of the Kolmogorov function, J. Symbolic Logic 71 (2006), no. 2, 501–528. MR 2225891, DOI 10.2178/jsl/1146620156
- Noam Greenberg and Joseph S. Miller, Lowness for Kurtz randomness, J. Symbolic Logic 74 (2009), no. 2, 665–678. MR 2518817, DOI 10.2178/jsl/1243948333
- Carl G. Jockusch Jr., Degrees of functions with no fixed points, Logic, methodology and philosophy of science, VIII (Moscow, 1987) Stud. Logic Found. Math., vol. 126, North-Holland, Amsterdam, 1989, pp. 191–201. MR 1034562, DOI 10.1016/S0049-237X(08)70045-4
- M. I. Kanovič, The complexity of the enumeration and solvability of predicates, Dokl. Akad. Nauk SSSR 190 (1970), 23–26 (Russian). MR 0262084
- M. I. Kanovič, The complexity of the reduction of algorithms, Dokl. Akad. Nauk SSSR 186 (1969), 1008–1009 (Russian). MR 0262082
- Bjørn Kjos-Hanssen, André Nies, and Frank Stephan, Lowness for the class of Schnorr random reals, SIAM J. Comput. 35 (2005), no. 3, 647–657. MR 2201451, DOI 10.1137/S0097539704446323
- 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, DOI 10.1007/978-1-4757-2606-0
- Ming Li and Paul Vitányi, An introduction to Kolmogorov complexity and its applications, 3rd ed., Texts in Computer Science, Springer, New York, 2008. MR 2494387, DOI 10.1007/978-0-387-49820-1
- Joseph Stephen Miller, Pi-$0$-$1$ classes in computable analysis and topology, 2002. Ph.D. thesis, Cornell University.
- André Nies, 2004. Private communication.
- Frank Stephan and Liang Yu, Lowness for weakly 1-generic and Kurtz-random, Theory and applications of models of computation, Lecture Notes in Comput. Sci., vol. 3959, Springer, Berlin, 2006, pp. 756–764. MR 2279138, DOI 10.1007/11750321_{7}2
Additional Information
- Bjørn Kjos-Hanssen
- Affiliation: Department of Mathematics, University of Hawaii at Mānoa, 2565 McCarthy Mall, Honolulu, Hawaii 96822
- Email: bjoern@math.hawaii.edu
- Wolfgang Merkle
- Affiliation: Institut für Informatik, Ruprecht-Karls-Universität Heidelberg, Im Neuenheimer Feld 294, 69120 Heidelberg, Germany
- Email: merkle@math.uni-heidelberg.de
- Frank Stephan
- Affiliation: Departments of Computer Science and Mathematics, National University of Singapore, 3 Science Drive 2, Singapore 117543, Republic of Singapore
- MR Author ID: 335879
- ORCID: 0000-0001-9152-1706
- Email: fstephan@comp.nus.edu.sg
- Received by editor(s): December 23, 2009
- Received by editor(s) in revised form: February 2, 2010
- Published electronically: April 27, 2011
- Additional Notes: The first author was partially supported by NSF-USA grants DMS-0652669 and DMS-0901020.
- © Copyright 2011 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 363 (2011), 5465-5480
- MSC (2010): Primary 03D28, 03D32, 68Q30
- DOI: https://doi.org/10.1090/S0002-9947-2011-05306-7
- MathSciNet review: 2813422