Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Kolmogorov complexity and the Recursion Theorem


Authors: Bjørn Kjos-Hanssen, Wolfgang Merkle and Frank Stephan
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
Published electronically: April 27, 2011
MathSciNet review: 2813422
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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 (2006c:03061)
  • [2] Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, and Leen Torenvliet, Enumerations of the Kolmogorov function, J. Symbolic Logic 71 (2006), no. 2, 501-528. MR 2225891 (2007b:68086)
  • [3] Cristian S. Calude, 2005. Private communication.
  • [4] Noam Greenberg and Joseph S. Miller, Lowness for Kurtz randomness, J. Symbolic Logic 74 (2009), no. 2, 665-678. MR 2518817 (2010b:03050)
  • [5] 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 (91c:03036)
  • [6] M. I. Kanovič, The complexity of the enumeration and solvability of predicates, Dokl. Akad. Nauk SSSR 190 (1970), 23-26 (Russian). MR 0262084 (41:6694)
  • [7] M. I. Kanovič, The complexity of the reduction of algorithms, Dokl. Akad. Nauk SSSR 186 (1969), 1008-1009 (Russian). MR 0262082 (41:6692)
  • [8] 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 (electronic), 10.1137/S0097539704446323. MR 2201451 (2006j:68051)
  • [9] 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 (97k:68086)
  • [10] 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 (2010c:68058)
  • [11] Joseph Stephen Miller, Pi-0-$ 1$ classes in computable analysis and topology, 2002. Ph.D. thesis, Cornell University.
  • [12] André Nies, 2004. Private communication.
  • [13] 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 (2007h:03073)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 03D28, 03D32, 68Q30

Retrieve articles in all journals with MSC (2010): 03D28, 03D32, 68Q30


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
Email: fstephan@comp.nus.edu.sg

DOI: https://doi.org/10.1090/S0002-9947-2011-05306-7
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.
Article copyright: © Copyright 2011 American Mathematical Society

American Mathematical Society