[14] In Example 2.2.5 we call x an n-string if x has length n and x = n00 ... 0.

(a) Show that there is a constant c such that for all n, every n-string x has complexity C(x|n) ≤

c. (Of course, c depends on the reference Turing machine U used to define C.)

(b) Show there is a constant c such that for all n, C(x|n) ≤ c for every x in the form of the n-length prefix of nn . . . n.

(c) Let c be as in Item (a). Consider some n and some string x of length n with C(x|n)

c. Prove that the extension of x to a string y = x00 ... 0 of length x has complexity C(y|x) ≤

c. Conclude that there is a constant c such that each string x, no matter how high its C(x|l(x)) complexity, can be extended to a string y with C(y|l(y)) ≤ c.

Comments. The C(x) measure contains the information about the pattern of 0s and 1s in x and information about the length n of x. For random such n, the complexity C(n) = l(n) + O(1) is about log n. In this case, about log n bits of the shortest program p for x will be used to account for x’s length. For n’s that are easy to compute, this is much less. This seems a minor problem at high complexities, but becomes an issue at low complexities, as follows. If the quantities of information related to the pattern only is low, say less than log n, for two strings x and y of length n, then distinctions between these quantities for x and y may get blurred in the comparison between C(x) and C(y) if the quantity of information related to length n dominates in both. The C(x|l(x)) complexity was meant to measure the information content of x apart from its length. However, as the present exercise shows, in that case l(x) may contain already the complete description of x up to a constant number of bits. Source: [D.W. Loveland, Inform. Contr., 15(1969), 510–526].