Kolmogorov complexity and the Recursion Theorem
Authors:
Bjørn KjosHanssen, Wolfgang Merkle and Frank Stephan
Journal:
Trans. Amer. Math. Soc. 363 (2011), 54655480
MSC (2010):
Primary 03D28, 03D32, 68Q30
Published electronically:
April 27, 2011
MathSciNet review:
2813422
Fulltext 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 wttcompute 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 PAcomplete, 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
AmbosSpies, Bjørn
KjosHanssen, Steffen
Lempp, and Theodore
A. Slaman, Comparing DNR and WWKL, J. Symbolic Logic
69 (2004), no. 4, 1089–1104. MR 2135656
(2006c:03061), 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
(2007b:68086), 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
(2010b:03050), 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, NorthHolland, Amsterdam, 1989,
pp. 191–201. MR 1034562
(91c:03036), 10.1016/S0049237X(08)700454
 [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
KjosHanssen, André
Nies, and Frank
Stephan, Lowness for the class of Schnorr random reals, SIAM
J. Comput. 35 (2005), no. 3, 647–657. MR 2201451
(2006j:68051), 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,
SpringerVerlag, 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, Pi0 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 1generic and Kurtzrandom, Theory and
applications of models of computation, Lecture Notes in Comput. Sci.,
vol. 3959, Springer, Berlin, 2006, pp. 756–764. MR 2279138
(2007h:03073), 10.1007/11750321_72
 [1]
 Klaus AmbosSpies, Bjørn KjosHanssen, Steffen Lempp, and Theodore A. Slaman, Comparing DNR and WWKL, J. Symbolic Logic 69 (2004), no. 4, 10891104. 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, 501528. 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, 665678. 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, NorthHolland, Amsterdam, 1989, pp. 191201. MR 1034562 (91c:03036)
 [6]
 M. I. Kanovič, The complexity of the enumeration and solvability of predicates, Dokl. Akad. Nauk SSSR 190 (1970), 2326 (Russian). MR 0262084 (41:6694)
 [7]
 M. I. Kanovič, The complexity of the reduction of algorithms, Dokl. Akad. Nauk SSSR 186 (1969), 10081009 (Russian). MR 0262082 (41:6692)
 [8]
 Bjørn KjosHanssen, André Nies, and Frank Stephan, Lowness for the class of Schnorr random reals, SIAM J. Comput. 35 (2005), no. 3, 647657 (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, SpringerVerlag, 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, Pi0 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 generic and Kurtzrandom, Theory and applications of models of computation Lecture Notes in Comput. Sci., vol. 3959, Springer, Berlin, 2006, pp. 756764. 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 KjosHanssen
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, RuprechtKarlsUniversität Heidelberg, Im Neuenheimer Feld 294, 69120 Heidelberg, Germany
Email:
merkle@math.uniheidelberg.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:
http://dx.doi.org/10.1090/S000299472011053067
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 NSFUSA grants DMS0652669 and DMS0901020.
Article copyright:
© Copyright 2011
American Mathematical Society
