[43]

(a) Show that the minimal length of a program enumerating a set A (prints all elements of A in lexicographic length-increasing order and no other elements; we do not require halting in case A is finite)

is bounded above by three times the negative logarithm of the probability that a random program enumerates A. That is, the probability that if the input to the reference universal prefix machine is determined by flips of a fair coin, then the output is an enumeration of A.

(b) Show that the constant 3 in Item

(a) can be reduced to 2 for finite sets A.

Comments. Source for Item (a): [R.M. Solovay, Non-Classical Logics, Model Theory and Computability, A.I. Aruda, N.C.A. da Costa and R.

Chaqui, eds., North-Holland, 1977, 283–307]; for Item

(b) [N.K. Vereshchagin, Inform. Process. Lett., 103:1(2007), 34–37].