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

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 can wtt-compute a DNR function iff there is a nontrivial recursive lower bound on the Kolmogorov complexity of the initial segments of . Furthermore, can Turing compute a DNR function iff there is a nontrivial -recursive lower bound on the Kolmogorov complexity of the initial segments of . is PA-complete, that is, can compute a -valued DNR function, iff can compute a function such that is a string of length and maximal -complexity among the strings of length . iff can compute a function such that is a string of length and maximal -complexity among the strings of length . 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.

**[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**, 10.2178/jsl/1102022212**[2]**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**, 10.2178/jsl/1146620156**[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**, 10.2178/jsl/1243948333**[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**, 10.1016/S0049-237X(08)70045-4**[6]**M. I. Kanovič,*The complexity of the enumeration and solvability of predicates*, Dokl. Akad. Nauk SSSR**190**(1970), 23–26 (Russian). MR**0262084****[7]**M. I. Kanovič,*The complexity of the reduction of algorithms*, Dokl. Akad. Nauk SSSR**186**(1969), 1008–1009 (Russian). MR**0262082****[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. MR**2201451**, 10.1137/S0097539704446323**[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****[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****[11]**Joseph Stephen Miller,*Pi-0- 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**, 10.1007/11750321_72

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