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