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

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

**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.

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

(6) |

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 .