Kolmogorov complexity and the Recursion Theorem

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.