Generalized Kolmogorov Complexity for EOMs and GTMs

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

$$K_T(x) = \min_p\{l(p): T(p) \leadsto x \}$$

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 U^C ($T \in C$). We drop the index T, writing

$$K^C(x) = K_{U^C}(x) \leq K_T(x) + O(1).$$

This is justified by an appropriate Invariance Theorem [#!Kolmogorov:65!#,#!Solomonoff:64!#,#!Chaitin:69!#]: there is a positive constant c such that $K_{U^C}(x) \leq K_T(x) + c$ for all x, since the size of the compiler that translates arbitrary programs for T into equivalent programs for U^C does not depend on x.

Definition 3.4 (tex2html_wrap_inline$Km_T,Km^M,Km^E,Km^G$)   Given TM T and $x \in B^*$, define

$$Km_T(x) = \min_p\{l(p) : T(p) \leadsto xy, y \in B^{\sharp} \}.$$ (7)

Consider Def. 2.4. If C denotes a set of TMs with universal TM U^C, then define Km^C(x) = Km_U^C(x).

Km^C is a generalization of Schnorr's [#!Schnorr:73!#] and Levin's [#!Levin:73a!#] complexity measure Km^M 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 = $1 \over K(x)$ is even enumerable. Even K^E(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 ( $i = 1, 2, \ldots$); 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 $\succ x$, 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 K^E(x) by the length of the shortest element of L. This estimate will eventually stabilize forever.

Theorem 3.1   K^G(x) is not describable.  

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

$$h(x)= max_y \{K^G(y): 1 \leq y \leq g(x) \},$$ (8)

where g is any fixed recursive function, and also

$$f(x)= min_y \{y: K^G(y) = h(x) \}.$$ (9)

Since the number of descriptions p with l(p) < n-O(1) cannot exceed 2^n-O(1), but the number of strings x with l(x) = n equals 2ⁿ, most x cannot be compressed by more than O(1) bits; that is, $K^G(x) \geq log~x - O(1)$ for most x. From (9) we therefore obtain K^G(f(x)) > log g(x) - O(1) for large enough x, because f(x) picks out one of the incompressible $y \leq g(x)$. However, obviously we also would have $K^G(f(x)) \leq l(x) + 2log~l(x) + O(1)$, using the encoding of Def. 2.8. Contradiction for quickly growing g with low complexity, such as g(x)=2^2x. $\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