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 |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1813399522 | ||
| 003 | DE-627 | ||
| 005 | 20230710123454.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 220808s2011 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1090/S0002-9947-2011-05306-7 |2 doi | |
| 035 | |a (DE-627)1813399522 | ||
| 035 | |a (DE-599)KXP1813399522 | ||
| 035 | |a (OCoLC)1389793489 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 28 |2 sdnb | ||
| 100 | 1 | |a Kjos-Hanssen, Bjørn |e VerfasserIn |0 (DE-588)1176728318 |0 (DE-627)1047753820 |0 (DE-576)516776789 |4 aut | |
| 245 | 1 | 0 | |a Kolmogorov complexity and the Recursion Theorem |c Bjørn Kjos-Hanssen, Wolfgang Merkle, and Frank Stephan |
| 264 | 1 | |c April 27, 2011 | |
| 300 | |a 16 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Gesehen am 08.08.2022 | ||
| 520 | |a 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. | ||
| 700 | 1 | |a Merkle, Wolfgang |e VerfasserIn |0 (DE-588)1049898400 |0 (DE-627)782852831 |0 (DE-576)40388201X |4 aut | |
| 700 | 1 | |a Stephan, Frank |e VerfasserIn |0 (DE-588)1125914025 |0 (DE-627)880490810 |0 (DE-576)483630047 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |a American Mathematical Society |t Transactions of the American Mathematical Society |d Providence, RI : Soc., 1900 |g 363(2011), 10, Seite 5465-5480 |h Online-Ressource |w (DE-627)269247351 |w (DE-600)1474637-2 |w (DE-576)079876110 |x 1088-6850 |7 nnas |
| 773 | 1 | 8 | |g volume:363 |g year:2011 |g number:10 |g pages:5465-5480 |g extent:16 |a Kolmogorov complexity and the Recursion Theorem |
| 856 | 4 | 0 | |u https://doi.org/10.1090/S0002-9947-2011-05306-7 |x Verlag |x Resolving-System |z lizenzpflichtig |3 Volltext |
| 856 | 4 | 0 | |u https://www.ams.org/tran/2011-363-10/S0002-9947-2011-05306-7/ |x Verlag |z lizenzpflichtig |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20220808 | ||
| 993 | |a Article | ||
| 994 | |a 2011 | ||
| 998 | |g 1049898400 |a Merkle, Wolfgang |m 1049898400:Merkle, Wolfgang |d 110000 |d 110300 |e 110000PM1049898400 |e 110300PM1049898400 |k 0/110000/ |k 1/110000/110300/ |p 2 | ||
| 999 | |a KXP-PPN1813399522 |e 4176773774 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"type":{"media":"Online-Ressource","bibl":"article-journal"},"note":["Gesehen am 08.08.2022"],"language":["eng"],"recId":"1813399522","person":[{"role":"aut","display":"Kjos-Hanssen, Bjørn","roleDisplay":"VerfasserIn","given":"Bjørn","family":"Kjos-Hanssen"},{"family":"Merkle","given":"Wolfgang","display":"Merkle, Wolfgang","roleDisplay":"VerfasserIn","role":"aut"},{"family":"Stephan","given":"Frank","roleDisplay":"VerfasserIn","display":"Stephan, Frank","role":"aut"}],"title":[{"title_sort":"Kolmogorov complexity and the Recursion Theorem","title":"Kolmogorov complexity and the Recursion Theorem"}],"physDesc":[{"extent":"16 S."}],"relHost":[{"title":[{"title":"Transactions of the American Mathematical Society","title_sort":"Transactions of the American Mathematical Society"}],"note":["Gesehen am 09.07.24"],"type":{"bibl":"periodical","media":"Online-Ressource"},"disp":"American Mathematical SocietyTransactions of the American Mathematical Society","recId":"269247351","language":["eng"],"corporate":[{"display":"American Mathematical Society","roleDisplay":"VerfasserIn","role":"aut"}],"pubHistory":["1.1900 -"],"part":{"extent":"16","volume":"363","text":"363(2011), 10, Seite 5465-5480","issue":"10","pages":"5465-5480","year":"2011"},"origin":[{"dateIssuedDisp":"1900-","publisher":"Soc.","dateIssuedKey":"1900","publisherPlace":"Providence, RI"}],"id":{"issn":["1088-6850"],"eki":["269247351"],"zdb":["1474637-2"]},"physDesc":[{"extent":"Online-Ressource"}]}],"name":{"displayForm":["Bjørn Kjos-Hanssen, Wolfgang Merkle, and Frank Stephan"]},"origin":[{"dateIssuedKey":"2011","dateIssuedDisp":"April 27, 2011"}],"id":{"doi":["10.1090/S0002-9947-2011-05306-7"],"eki":["1813399522"]}} | ||
| SRT | |a KJOSHANSSEKOLMOGOROV2720 | ||