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 U^{C} ().
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 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 ,
define

(7)

Consider Def. 2.4.
If C denotes a set of TMs with universal TM U^{C}, then define
Km^{C}(x) = Km_{UC}(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 =
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 (
); 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 K^{E}(x) by the length of the
shortest element of L. This estimate will eventually stabilize forever.

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

Proof. Identify finite bitstrings with the integers they represent.
If K^{G}(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
2^{n-O(1)}, but the number of strings x with l(x) = n equals 2^{n},
most x cannot be compressed by more than O(1) bits; that is,
for most x.
From (9) we
therefore obtain
K^{G}(f(x)) > logg(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)=2^{2x}.