[42] Consider x(i) as a two-argument function as in Example 5.5.12. (a) Show that the function x(i) is computable from x, i given an oracle

[42] Consider βx(i) as a two-argument function as in Example 5.5.12.

(a) Show that the function βx(i) is computable from x, i given an oracle for the halting problem.

(b) Show that the function βx(i) is upper semicomputable from x, i, K(x)

up to a logarithmic error.

(c) Show that the set {(x, S, β) : x ∈ S, δ(x|S) < β} is not computably enumerable.

(d) Show that βx(i) is not lower semicomputable to within precision l(x)/3 (there is no lower semicomputable function f(i) such that |f(i)−

βx(i)| ≤ l(x)/3); and

(e) Show that βx(i) is not upper semicomputable to within precision l(x)/ log4 l(x). (There is no upper semicomputable function f(i) such that |f(i) − βx(i)| ≤ l(x)/ log4 l(x)).

Comments. Hint for Item (a): Run all programs of length ≤ i dovetailed fashion and find all finite sets S containing x that are produced. With respect to all these sets determine the conditional complexity K(x|S)

and hence the randomness deficiency δ(x|S). Taking the minimum, we obtain βx(i). All these things are possible using information from the halting problem to determine whether a given program will terminate.

Hint for Item (b): This follows from the upper semicomputability of

λx(i) and Theorem 5.5.1.

Items

(d) and

(e) show that the function βx(i)

is not semicomputable, not even within a large margin of error. Source:

[N.K. Vereshchagin and P.M.B. Vit´anyi, Ibid.].