
{"id":30,"date":"2011-05-10T22:19:53","date_gmt":"2011-05-11T08:19:53","guid":{"rendered":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/?p=30"},"modified":"2025-10-19T17:37:29","modified_gmt":"2025-10-20T03:37:29","slug":"kolmogorov-complexity-and-the-recursion-theorem","status":"publish","type":"post","link":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/kolmogorov-complexity-and-the-recursion-theorem\/","title":{"rendered":"Kolmogorov complexity and the recursion theorem"},"content":{"rendered":"<p>Kolmogorov complexity and the recursion theorem (with Wolfgang Merkle and Frank Stephan). <span class=\"newjournal\">Transactions of the American Mathematical Society<\/span><b>363<\/b> (2011) no. 10, 5465\u20145480.<br \/>\narXiv:<a href=\"http:\/\/arxiv.org\/abs\/0901.3933\">0901.3933<\/a>. Preliminary version in STACS 2006,<i> Lecture Notes in Computer Science,<\/i><br \/>\nvol. 3884, Springer, Berlin, 2006, pp. 149\u2014161.<\/p>\n<p>The groundwork for this paper was laid in Berkeley in 2004 while Merkle and I were both stopping by there. The paper fits in a long line of results saying &#8220;DNR is equivalent to&#8230;&#8221;, in this case to computing a real whose initial segment complexity is sufficiently high.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Kolmogorov complexity and the recursion theorem (with Wolfgang Merkle and Frank Stephan). Transactions of the American Mathematical Society363 (2011) no. 10, 5465\u20145480. arXiv:0901.3933. Preliminary version in STACS 2006, Lecture Notes in Computer Science, vol. 3884, Springer, Berlin, 2006, pp. 149\u2014161. The groundwork for this paper was laid in Berkeley in 2004 while Merkle and I &hellip; <a href=\"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/kolmogorov-complexity-and-the-recursion-theorem\/\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Kolmogorov complexity and the recursion theorem<\/span> <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8,6],"tags":[],"class_list":["post-30","post","type-post","status-publish","format-standard","hentry","category-computability","category-publications"],"_links":{"self":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/posts\/30","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/comments?post=30"}],"version-history":[{"count":5,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/posts\/30\/revisions"}],"predecessor-version":[{"id":9098784,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/posts\/30\/revisions\/9098784"}],"wp:attachment":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/media?parent=30"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/categories?post=30"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/tags?post=30"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}