Chain rule for Kolmogorov complexity: Difference between revisions

Revision as of 18:58, 22 December 2006

Revision as of 19:00, 22 December 2006

Line 37:

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

produced. We can restrict to <math>A_x</math> simply by ignoring any output where <math>u \ne