Kolmogorov complexity and the Recursion Theorem
Bjørn Kjos-Hanssen, Wolfgang Merkle, Frank Stephan · 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 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 A . Furthermore, A A can Turing compute a DNR function iff there is a nontrivial A A -recursive lower bound on the Kolmogorov complexity of the initial segments of A A . A A is PA-complete, that is, A A can compute a { 0 , 1 } \{0,1\} -valued DNR function, iff A A can compute a function F F such that F ( n ) F(n) is a string of length n n and maximal C C -complexity among the strings of length n n . A ≥ T K A \geq _T K iff A A can compute a function F F such that