Kolmogorov complexity and the Recursion Theorem
Several classes of diagonally nonrecursive (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. Furtherm...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
April 27, 2011
|
| In: |
Transactions of the American Mathematical Society
Year: 2011, Volume: 363, Issue: 10, Pages: 5465-5480 |
| ISSN: | 1088-6850 |
| DOI: | 10.1090/S0002-9947-2011-05306-7 |
| Online Access: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1090/S0002-9947-2011-05306-7 Verlag, lizenzpflichtig, Volltext: https://www.ams.org/tran/2011-363-10/S0002-9947-2011-05306-7/ 
|
| Author Notes: | Bjørn Kjos-Hanssen, Wolfgang Merkle, and Frank Stephan |
| Summary: | Several classes of diagonally nonrecursive (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 segments 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≥TK 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 no longer permit the usage of the Recursion Theorem. |
|---|---|
| Item Description: | Gesehen am 08.08.2022 |
| Physical Description: | Online Resource |
| ISSN: | 1088-6850 |
| DOI: | 10.1090/S0002-9947-2011-05306-7 |