# Kolmogorov Complexity and Proof Techniques

I'm interested in examples of theorems that employ the proof techniques that are utilized in the proof of the undecidability of Kolmogorov Complexity.

Definition:(Sipser) Let x be a binary string. We say that the minimal description of x, written as d(x), is the shortest string $\langle$M,w$\rangle$ where TM M on input w halts with x on its tape. So, the Kolmogorov Complexity K(x) is written as, K(x)=|d(x)|. K(x) is defined to be the length of minimal description of x.

Theorem: K(x) is not a computable function.

Proof/Sketch of Proof (attributed to Chor): Proof by contradiction. $\forall$n, let $y_{n}$ be the lexicographical first string y that satisfies n < K(y). Consider the following TM M: On input n (encoded in binary), M generates one by one all binary strings $x_{0}$, $x_{1}$, $x_{2}$, $x_{3}$... in lexicographic order.

For each $x_{i}$ it produces, M computes K($x_{i}$).

If K($x_{i}$) > n, then the TM M, outputs $x_{i}$ and halts. Else, the TM M, continues to examine the next lexicographical string $x_{i+1}$.

Since the function K is unbounded, it is guaranteed that M will eventually come across a string x satisfying K(x) $>$ n.

Question: what will the TM M output on input n?

By definition on input n TM M outputs $y_{n}$ (the lexicographical first string whose Kolmogorov complexity exceeds n, K(x) > n), but the length of n is $log_{2}$(n). So we have $K_{M}$($y_{n}$) $\leq$ $log_{2}$(n). There is a constant $c_{M}$ such that $\forall$y, K(y) $\leq$ $K_{M}$(y) + $c_{M}$, so $\forall$n K($y_{n}$) $\leq$ $log_{2}$(n) + $c_{M}$.

By definition of $y_{n}$ for all n, n < K($y_{n}$). By combining the two inequalities we get: n < $log_{2}$(n) + $c_{M}$, but for large enough n this is false. Thus a contradiction.

Question: What other theorems utilize a similar proof technique in their proofs?

For example: The proof that the set of incompressible strings is undecidable is very similar with some slight modifications.

-
This looks like an application of the Berry paradox (en.wikipedia.org/wiki/Berry_paradox), in the same way that Gödel's incompleteness theorem and the halting problem are applications of the liar paradox. – George Lowther Jun 16 '11 at 21:52
Crossposted on cstheory - cstheory.stackexchange.com/questions/7226/… – François G. Dorais Jul 4 '11 at 11:34
CAL, you can probably undelete your post by following the above link. If you have trouble, flag the cstheory moderators and they will undelete the post for you. – François G. Dorais Jul 4 '11 at 13:05
In order to reduce any confusion I decided against cross-posting on cs theory, this way my question will be in one central location. Thanks François for all of your help. It is much appreciated. Kaveh made an excellent recommendation by pointing me to Ming Li and Paul Vitanyi's "An Introduction to Kolmogorov Complexity and Its Applications" – CAL Jul 5 '11 at 2:54