[27] We continue Exercise 5.2.11.

Let f1, f2,... be the standard enumeration of the partial computable functions.

(a) Give the implicit effective enumeration of the hypotheses for the prior P defined by P(Hi)=1/(i(i + 1)) and give the implicit incomputable enumeration according to the universal prior with the probability of Hi equal to m(i).

(b) Given an infinite sequence e1, e2,... of examples of fi, the speed of learning a function fi on that sequence is the minimal number m of examples e1,...,em that contain counterexamples to every function fj with j

Comments. Hint: Enumerate all hypotheses in two lists, one list H1, H2,...

according to decreasing P(Hi), and one list according to decreasing m(i), and use Gold’s learning by enumeration, Section 5.2.6.

Roughly speaking, the universal prior puts some simple hypotheses Hi with K(i) very small (sometimes incomputably) much closer to the beginning of the list, but it does not put any hypotheses Hi later in the list than position 2K(i) = O(i log2 i). Source: [M. Li and P.M.B. Vit´anyi, J. Comput.

System Sci., 44:2(1992), 343–384].