next up previous
Next: EOMs dominate MTMs Up: Complexity of Constructive Descriptions Previous: Generalized Kolmogorov Complexity for

Expressiveness of EOMs and GTMs

Since GTMs may occasionally rewrite parts of their output, they are computationally more expressive than MTMs in the sense that they permit much more compact descriptions of certain objects -- compare also [7]. For instance, $K(x) - K^G(x)$ is unbounded, as will be shown next. This will later have consequences for predictions, given certain observations.

Theorem 3.2   $K(x) - K^G(x)$ is unbounded.

Proof. Define
h'(x)= max_y \{K(y): 1 \leq y \leq g(x) \};   f'(x)= min_y \{y: K(y) = h'(x) \},
\end{displaymath} (8)

where $g$ is recursive. Then $K^G(f'(x)) = O(l(x) + K(g))$ (where $K(g)$ is the size of the minimal halting description of function $g$), but $K(f'(x)) > log g(x) -O(1)$ for sufficiently large $x$ -- compare the proof of Theorem 3.1. Therefore $K(f'(x)) - K^G(f'(x)) geq O(log g(x))$ for infinitely many $x$ and quickly growing $g$ with low complexity.


Juergen Schmidhuber 2003-02-13