Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Kolmogorov complexity and the Recursion Theorem   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.

31
The categories of this paper are: ao-sci
22
The categories of this paper are: chao-dyn
3
The categories of this paper are: physics
5
The categories of this paper are: gr-qc
9
The categories of this paper are: nlin
0
The categories of this paper are: hep-ph
4
The categories of this paper are: cond-mat
36
The categories of this paper are: cmp-lg
26
The categories of this paper are: bayes-an
1
The categories of this paper are: cs
20
The categories of this paper are: acc-phys
18
The categories of this paper are: econ
27
The categories of this paper are: comp-gas
11
The categories of this paper are: hep-lat
19
The categories of this paper are: eess
33
The categories of this paper are: plasm-ph