Kolmogorov complexity: Difference between revisions

Revision as of 18:45, 4 April 2024

Revision as of 16:51, 27 May 2024

Line 352:

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 journal |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 |journal=Texts in Computer Science |language=en |at=Exercise 2.7.7. |doi=10.1007/978-0-387-49820-1 |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 {{clarify span|the [[Busy beaver|Busy Beaver]] shift function|reason=The article(also definesdenoted two functions, Σ andas <math>S. Which one is meant here? Better change 'BB' to the name used in the Busy Beaver article.|date=January 2024}}(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>.