• [39] How many objects are there of a given complexity n?

How many self-delimiting programs of length n are there? Let g(n) be the number of objects x with K(x) = n, and let Dn be the set of binary strings p of length n such that U(p) is defined. Define the moving average h(n, c)=1/(2c + 1)c i=−c g(n + i) + O(1).

(a) First show that 

y m(x, y) = Θ(m(x)).

(b) Show log d(Dn) = n − K(n) + O(1) (hence log n i=1 d(Di) = n −

K(n)+O(1)) and that there is a natural number c such that log h(n,

c) =

n − K(n).

Comments. Hint for Item (b): use Exercise 4.3.8 and Item (a). Since we are interested in equality only up to an additive constant, we can omit the normalizing factor 1/(2c+ 1) from the definition of h. But we do not know whether we can replace h by g. Namely, one can choose a reference prefix machine U such that g
(n) = 0 for all odd n. For instance, U
(00p) = U(p) of l(p) is even, U
(1p) = U(p) for l(p) is odd, and U
(p)
is undefined otherwise. Then U is defined only for inputs of even length, and for all x we have KU (x) ≤ K(x)+ 2. Source: [R.M. Solovay, Lecture Notes, 1975, unpublished; P. G´acs, Lecture Notes on Descriptional Complexity and Randomness, Manuscript, Boston University, 1987, 2008].