Kolmogorov complexity: Difference between revisions

Revision as of 12:18, 20 January 2025

Revision as of 03:05, 26 January 2025

Line 355:

If we have a halting oracle, then the Kolmogorov complexity of a string can be computed by simply trying every halting program, in lexicographic order, until one of them outputs the string.

The other direction is much more involved.<ref>{{Cite journal |last1=Chaitin |first1=G. |last2=Arslanov |first2=A. |last3=Calude |first3=Cristian S. |date=1995-09-01 |title=Program-size Complexity Computes the Halting Problem |journal=Bull. EATCS|s2cid=39718973 }}</ref><ref>{{Cite book |last1=Li |first1=Ming |last2=Vitányi |first2=Paul |date=2008 |title=An Introduction to Kolmogorov Complexity and Its Applications |url=https://link.springer.com/book/10.1007/978-0-387-49820-1 |journalseries=Texts in Computer Science |language=en |at=Exercise 2.7.7. |doi=10.1007/978-0-387-49820-1 |bibcode=2008ikca.book.....L |isbn=978-0-387-33998-6 |issn=1868-0941}}</ref> It shows that given a Kolmogorov complexity function, we can construct a function <math>p</math>, such that <math>p(n) \geq BB(n)</math> for all large <math>n</math>, where <math>BB</math> is the [[Busy beaver|Busy Beaver]] shift function (also denoted as <math>S(n)</math>). By modifying the function at lower values of <math>n</math> we get an upper bound on <math>BB</math>, which solves the halting problem.

Consider this program <math display="inline">p_K</math>, which takes input as <math display="inline">n</math>, and uses <math display="inline">K</math>.