Expressiveness of EOMs and GTMs
Next: EOMs More Expressive Than Up: Complexity of Constructive Descriptions Previous: Generalized Kolmogorov Complexity for

## Expressiveness of EOMs and GTMs

On their internal work tapes MTMs can compute whatever GTMs can compute. But they commit themselves forever once they print out some bit. They are ill-suited to the case where the output may require subsequent revision after time intervals unpredictable in advance -- compare Example 2.1. Alternative MTMs that print out sequences of result updates (separated by, say, commas) would compute other things besides the result, and hence not satisfy the don't compute anything else'' aspect of individual describability. Recall from the introduction that in a certain sense there are uncountably many collectively describable strings, but only countably many individually describable ones.

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. For instance, K(x) - KG(x) is unbounded, as will be seen next. This will later have consequences for predictions, given certain observations.

Theorem 3.2   K(x) - KG(x) is unbounded.

Proof. Define

 (10)

where g is recursive. Then KG(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 for infinitely many x and quickly growing g with low complexity.

Next: EOMs More Expressive Than Up: Complexity of Constructive Descriptions Previous: Generalized Kolmogorov Complexity for
Juergen Schmidhuber
2001-01-09

Related links: In the beginning was the code! - Zuse's thesis - Life, the universe, and everything - Generalized Algorithmic Information - Speed Prior - The New AI