Generalized Kolmogorov Complexity for EOMs and GTMs

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

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

Compare Schnorr's less general ``process complexity'' for MTMs [37,44].

Proposition 3.1 ($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 [25,40,13]: 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.3 ( $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} \}.$$ (5)

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 [37] and Levin's [28] complexity measure $Km^M$ for MTMs.

Describability of $K(x)$ and $K^E(x)$. $K(x)$ is not computable by a halting program [25,40,13], but obviously $G$-computable or describable; the $z$ with $0.z =$ $1 over K(x)$ is even c.e. Even $K^E(x)$ is describable for finite $x$, 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) \},$$ (6)

where $g$ is any fixed recursive function, and also

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

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, $K^G(x) geq log x - O(1)$ for most $x$. From (7) 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^{2^x}$.