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

## Generalized Kolmogorov Complexity for EOMs and GTMs

Definition 3.2 (Generalized tex2html_wrap_inline$K_T$)   Given any TM T, define

Compare Schnorr's process complexity'' for MTMs [#!Schnorr:73!#,#!Vyugin:98!#].

Definition 3.3 (tex2html_wrap_inline$K^M, K^E, K^G$ based on Invariance Theorem)   Consider Def. 2.4. Let C denote a set of TMs with universal TM UC (). We drop the index T, writing

This is justified by an appropriate Invariance Theorem [#!Kolmogorov:65!#,#!Solomonoff:64!#,#!Chaitin:69!#]: there is a positive constant c such that for all x, since the size of the compiler that translates arbitrary programs for T into equivalent programs for UC does not depend on x.

Definition 3.4 (tex2html_wrap_inline$Km_T,Km^M,Km^E,Km^G$)   Given TM T and , define

 (7)

Consider Def. 2.4. If C denotes a set of TMs with universal TM UC, then define KmC(x) = KmUC(x).

KmC is a generalization of Schnorr's [#!Schnorr:73!#] and Levin's [#!Levin:73a!#] complexity measure KmM for MTMs.

Describability issues. K(x) is not computable by a halting program [#!Kolmogorov:65!#,#!Solomonoff:64!#,#!Chaitin:69!#], but obviously G-computable or describable; the z with 0.z = is even enumerable. Even KE(x) is describable, using the following algorithm:

Run all EOM programs in dovetail style'' such that the n-th step of the i-th program is executed in the n+i-th phase ( ); whenever a program outputs x, place it (or its prefix read so far) in a tentative list L of x-computing programs or program prefixes; whenever an element of L produces output , delete it from L; whenever an element of L requests an additional input bit, update L accordingly. After every change of L replace the current estimate of KE(x) by the length of the shortest element of L. This estimate will eventually stabilize forever.

Theorem 3.1   KG(x) is not describable.

Proof. Identify finite bitstrings with the integers they represent. If KG(x) were describable then also

 (8)

where g is any fixed recursive function, and also

 (9)

Since the number of descriptions p with l(p) < n-O(1) cannot exceed 2n-O(1), but the number of strings x with l(x) = n equals 2n, most x cannot be compressed by more than O(1) bits; that is, for most x. From (9) we therefore obtain KG(f(x)) > log g(x) - O(1) for large enough x, because f(x) picks out one of the incompressible . However, obviously we also would have , using the encoding of Def. 2.8. Contradiction for quickly growing g with low complexity, such as g(x)=22x.

Next: Expressiveness of EOMs and Up: Complexity of Constructive Descriptions Previous: Complexity of Constructive Descriptions
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