Editing Kolmogorov complexity (section)

== Halting problem ==
The Kolmogorov complexity function is equivalent to deciding the halting problem.

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 |series=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>.

* List all strings of length <math display="inline">\leq 2n + 1</math>.
* For each such string <math display="inline">x</math>, enumerate all (prefix-free) programs of length <math>K(x)</math> until one of them does output <math display="inline">x</math>. Record its runtime <math display="inline">n_x</math>.
* Output the largest <math display="inline">n_x</math>.

We prove by contradiction that <math display="inline">p_K(n) \geq BB(n)</math> for all large <math display="inline">n</math>.

Let <math display="inline">p_{n}</math> be a Busy Beaver of length <math>n</math>. Consider this (prefix-free) program, which takes no input:

* Run the program <math display="inline">p_{n}</math>, and record its runtime length <math display="inline">BB(n)</math>.
* Generate all programs with length <math display="inline">\leq 2n</math>. Run every one of them for up to <math display="inline">BB(n)</math> steps. Note the outputs of those that have halted.
* Output the string with the lowest lexicographic order that has not been output by any of those.

Let the string output by the program be <math display="inline">x</math>.

The program has length <math display="inline">\leq n + 2\log_2 n + O(1)</math>, where <math>n</math> comes from the length of the Busy Beaver <math display="inline">p_{n}</math>, <math>2\log_2 n</math> comes from using the (prefix-free) [[Elias delta code]] for the number <math>n</math>, and <math>O(1)</math> comes from the rest of the program. Therefore,<math display="block">K(x) \leq n + 2\log_2 n + O(1) \leq 2n</math>for all big <math display="inline">n</math>. Further, since there are only so many possible programs with length <math display="inline">\leq 2n</math>, we have <math display="inline">l(x) \leq 2n + 1</math> by [[pigeonhole principle]].
By assumption, <math display="inline">p_K(n) < BB(n)</math>, so every string of length <math display="inline">\leq 2n + 1</math> has a minimal program with runtime <math display="inline">< BB(n)</math>. Thus, the string <math display="inline">x</math> has a minimal program with runtime <math display="inline">< BB(n)</math>. Further, that program has length <math display="inline">K(x) \leq 2n</math>. This contradicts how <math display="inline">x</math> was constructed.