Kolmogorov complexity and the Recursion Theorem
arXiv:0901.3933 · doi:10.1090/S0002-9947-2011-05306-7
Abstract
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.
Full version of paper presented at STACS 2006, Lecture Notes in Computer Science 3884 (2006), 149--161
References in corpus (2)
Cited by in corpus (25)
- Martin-Löf randomness and Galton-Watson processes
- Somewhere over the rainbow Ramsey theorem for pairs
- Higher Kurtz randomness
- Generalizations of the Recursion Theorem
- Arithmetic complexity via effective names for random sequences
- Randomness for computable measures and initial segment complexity
- Muchnik degrees and cardinal characteristics
- Randomness extraction and asymptotic Hamming distance
- Intrinsic Smallness
- Partition genericity and pigeonhole basis theorems
- Upper bound on some hightness notions
- Effective bi-immunity and randomness
- Demuth's path to randomness
- From eventually different functions to pandemic numberings
- On the Hausdorff dimension of maximal chains and antichains of Turing and Hyperarithmetic degrees
- Avoid Schnorr randomness
- Index Sets of Universal Codes
- Computable analogs of cardinal characteristics: Prediction and Rearrangement
- Depth, Highness and DNR degrees
- Diagonally non-computable functions and fireworks
- Which DNR can be minimal
- Pointed computations and Martin-Löf randomness
- Effective randomness, strong reductions and Demuth's theorem
- Solovay functions and their applications in algorithmic randomness
- Complexity and Avoidance