next up previous
Next: Measures and Probability Distributions Up: Complexity of Constructive Descriptions Previous: Which is the ``True''

Relation to Conditional Complexity

For $x in B^*$, the nonapproximable $K^G(x)$ can also be rewritten as $K^G(x) = K(x mid Omega)$ (Peter Gács, personal communication, 2001). What about the approximable and thus more accessible $K^E(x)$? It may be of interest to identify and examine the $y$ in $K^E(x) = K(x mid y)$.

Juergen Schmidhuber 2003-02-13