Chain rule for Kolmogorov complexity: Difference between revisions

Revision as of 18:55, 22 December 2006

Revision as of 18:58, 22 December 2006

Line 33:

construction of the set <math>A = \{(u,z) : K(u,z) \le K(x,y)\}</math>; that is, the

construction of the set of all pairs <math>(u,z)</math> such that the shortest input (for

a [[universal Turing machine]]) that produces <math>(u,z)</math> (and some way to distinguish

<math>u</math> from <math>z</math>) is shorter than the shortest producing <math>(x,y)</math>. We will also

need <math>A_x = \{z: K(x,z) \le K(x,y)\}</math>, the subset of <math>A</math> where <math>z = u</math>.

[[recursively enumerable|Enumerating]] <math>A</math> is not hard (although not fast!). In parallel, simulate all

</math>2^{K(x,y)}</math> programs with length <math>\le K(x,y)</math>. Output each <math>u,z</math> as the

simulated program terminates; eventually, any particular such <math>u,z</math> will be

Line 87:

where the first inequality follows since each element of <math>U</math> corresponds to an

</math>A_u</math> with strictly more than <math>2^e</math> elements.

But this leads to a contradiction: