stylistic:style_transfer, linguistic:paraphrasing
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. It shows that given a Kolmogorov complexity function, we can construct a function p {\displaystyle p}, such that p (n) ≥ B B (n) {\displaystyle p(n)\geq BB(n)} for all large n {\displaystyle n}, where B B {\displaystyle BB} is the Busy Beaver shift function (also denoted as S (n) {\displaystyle S(n)}). By modifying the function at lower values of n {\displaystyle n} we get an upper bound on B B {\displaystyle BB}, which solves the halting problem.

Consider this program p K {\textstyle p_{K}}, which takes input as n {\textstyle n}, and uses K {\textstyle K}.

We prove by contradiction that p K (n) ≥ B B (n) {\textstyle p_{K}(n)\geq BB(n)} for all large n {\textstyle n}.

Let p n {\textstyle p_{n}} be a Busy Beaver of length n {\displaystyle n}. Consider this (prefix-free) program, which takes no input:

Let the string output by the program be x {\textstyle x}.

The program has length ≤ n + 2 log 2 n + O (1) {\textstyle \leq n+2\log _{2}n+O(1)}, where n {\displaystyle n} comes from the length of the Busy Beaver p n {\textstyle p_{n}}, 2 log 2 n {\displaystyle 2\log _{2}n} comes from using the (prefix-free) Elias delta code for the number n {\displaystyle n}, and O (1) {\displaystyle O(1)} comes from the rest of the program. Therefore, K (x) ≤ n + 2 log 2 n + O (1) ≤ 2 n {\displaystyle K(x)\leq n+2\log _{2}n+O(1)\leq 2n} for all big n {\textstyle n}. Further, since there are only so many possible programs with length ≤ 2 n {\textstyle \leq 2n}, we have l (x) ≤ 2 n + 1 {\textstyle l(x)\leq 2n+1} by pigeonhole principle.By assumption, p K (n) < B B (n) {\textstyle p_{K}(n)<BB(n)}, so every string of length ≤ 2 n + 1 {\textstyle \leq 2n+1} has a minimal program with runtime < B B (n) {\textstyle <BB(n)}. Thus, the string x {\textstyle x} has a minimal program with runtime < B B (n) {\textstyle <BB(n)}. Further, that program has length K (x) ≤ 2 n {\textstyle K(x)\leq 2n}. This contradicts how x {\textstyle x} was constructed.