Kolmogorov Complexity and Proof Techniques - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T12:40:26Z http://mathoverflow.net/feeds/question/68006 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/68006/kolmogorov-complexity-and-proof-techniques Kolmogorov Complexity and Proof Techniques CAL 2011-06-16T21:31:28Z 2012-04-03T16:25:33Z <p>I'm interested in examples of theorems that employ the proof techniques that are utilized in the proof of the undecidability of Kolmogorov Complexity. </p> <p><strong>Definition:(Sipser)</strong> 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.</p> <p><strong>Theorem:</strong> K(x) is not a computable function.</p> <p><strong>Proof/Sketch of Proof (attributed to Chor):</strong> Proof by contradiction. $\forall$n, let $y_{n}$ be the lexicographical first string y that satisfies n &lt; 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.</p> <p>For each $x_{i}$ it produces, M computes K($x_{i}$).</p> <p>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}$.</p> <p>Since the function K is unbounded, it is guaranteed that M will eventually come across a string x satisfying K(x) $>$ n.</p> <p>Question: what will the TM M output on input n? </p> <p>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}$. </p> <p>By definition of $y_{n}$ for all n, n &lt; K($y_{n}$). By combining the two inequalities we get: n &lt; $log_{2}$(n) + $c_{M}$, but for large enough n this is false. Thus a contradiction.</p> <p><strong>Question:</strong> What other theorems utilize a similar proof technique in their proofs?</p> <p>For example: The proof that the set of incompressible strings is undecidable is very similar with some slight modifications. </p> http://mathoverflow.net/questions/68006/kolmogorov-complexity-and-proof-techniques/93015#93015 Answer by jkun for Kolmogorov Complexity and Proof Techniques jkun 2012-04-03T16:25:33Z 2012-04-03T16:25:33Z <p>Using the same technique, one can construct infinitely many statements which are true with probability arbitrarily close to 1, but are nonetheless unprovable. See lemma 4 in <a href="http://theory.stanford.edu/~trevisan/cs172/notek.pdf" rel="nofollow">http://theory.stanford.edu/~trevisan/cs172/notek.pdf</a></p>