  Several classes of 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 segements 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 solves the halting problem 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 do no longer permit the
usage of the Recursion Theorem.
