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,
is unbounded, as will be shown next.
This will later have
consequences for predictions, given certain observations.
Theorem 3.2
is unbounded.
Proof.
Define
|
(8) |
where is recursive.
Then
(where is the size of the minimal
halting description of function ), but
for
sufficiently large --
compare the proof of Theorem 3.1.
Therefore
for infinitely many
and quickly growing with low complexity.
Subsections
Juergen Schmidhuber
2003-02-13