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 )   Given any TM T, define

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

Proposition 3.1 ( based on Invariance Theorem)   Consider Def. 2.4. Let denote a set of TMs with universal TM (). We drop the index , writing

This is justified by an appropriate Invariance Theorem [25,40,13]: there is a positive constant such that for all , since the size of the compiler that translates arbitrary programs for into equivalent programs for does not depend on .

Definition 3.3 ( )   Given TM and , define
 (5)

Consider Def. 2.4. If denotes a set of TMs with universal TM , then define

is a generalization of Schnorr's [37] and Levin's [28] complexity measure for MTMs.

Describability of and . is not computable by a halting program [25,40,13], but obviously -computable or describable; the with is even c.e. Even is describable for finite , using the following algorithm:

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

Theorem 3.1   is not describable.

Proof. Identify finite bitstrings with the integers they represent. If were describable then also

 (6)

where is any fixed recursive function, and also
 (7)

Since the number of descriptions with cannot exceed , but the number of strings with equals , most cannot be compressed by more than bits; that is, for most . From (7) we therefore obtain for large enough , because picks out one of the incompressible . However, obviously we also would have , using the encoding of Def. 2.8. Contradiction for quickly growing with low complexity, such as .

Next: Expressiveness of EOMs and Up: Complexity of Constructive Descriptions Previous: Complexity of Constructive Descriptions
Juergen Schmidhuber 2003-02-13