Kolmogorov complexity and the Recursion Theorem - Kjos-Hanssen, Bjørn; Merkle, Wolfgang; Stephan, Frank (Transactions of the American Mathematical Society, 2011)
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≥TK 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.
Gesehen am 08.08.2022