next up previous
Next: Relation to Conditional Complexity Up: Complexity of Constructive Descriptions Previous: GTMs dominate EOMs

Which is the ``True'' Information Content of $x$?

Traditionally, the algorithmic information conveyed by $x$ is identified with $K(x)$, the size of the shortest halting program of $x$. This makes a lot of sense, because we often want to limit ourselves to programs that at some point allow us to be sure that their output is complete. In the light of the results above, however, one might argue that the ``true'' information content of $x$ is actually embodied by the smaller $K^G(x)$, the size of the smallest nonhalting GTM program for $x$. $K^G(x)$ is not computable in the limit (Theorem 3.1), while $K(x)$ is. $K^E$ is between $K$ and $K^G$ in a certain sense -- it is ``closer'' to $K^G$ than $K$ while being ``just as computable in the limit'' as $K$.

Juergen Schmidhuber 2003-02-13