[34] Let X = x1, x2,... be a computable sequence of natural numbers (in N or the corresponding binary strings). The lower frequency of some element x in the sequence is defined as qX (x) = lim inf n→∞

1 n

d({i : i

(a) Show that there is a universal computable sequence U = u1, u2,...

such that for every computable sequence X = x1, x2,... there is a constant c > 0 such that cqU (x) ≥ qX (x), for all x in N .

(b) Show that if U and V are universal computable sequences, then qU (x) = Θ(qV (x)). Fix a reference universal computable sequence U, and define the a priori frequency of x as q(x) = qU (x).

(c) Show that q(x) = Θ(m(x)). (m(x) is the a priori probability of x.)

(d) A set is enumerable relative to 0 if it is the range of a function computable by an algorithm with an oracle for some computably enumerable set. An algorithm with an oracle for set A is an algorithm that (apart from the usual things) at each step can ask a question of the form, “is a in A?” and get the true answer “yes/no” for free. The computably enumerable sets correspond to the 0

-enumerable sets, where the oracle is restricted to computable sets. Define the notion of 0

-enumerable semimeasures, and show that there is a universal 0

-enumerable semimeasure p such that for each 0

-enumerable semimeasure ν there is a constant c > 0 such that p(x) ≥ cν(x). We call p the a priori probability relative to 0

.

(e) Show that p(x) = Θ(q(x)). Compare this with Item (c).

Comments. Source: [An.A. Muchnik, SIAM Theory Probab. Appl., 32 (1987), 513–514; A.N. Kolmogorov and V.A. Uspensky, SIAM Theory Probab. Appl., 32(1987), 389–412].