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) - K^G(x) is unbounded, as will be seen 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) \},$$ (10)

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. $\Box$

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