Kolmogorov complexity and the recursion theorem

Details Kolmogorov complexity and the recursion theorem Kolmogorov complexity and the recursion theorem

2009-01-26

arxiv.org/abs/0901.3933v1

Mathematics

Logic

Full version of paper presented at STACS 2006

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Kolmogorov complexity and the recursion theorem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Kolmogorov complexity and the recursion theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Kolmogorov complexity and the recursion theorem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-371522