[35] (a) Prove that the function x(i) is not upper semicomputable to within precision l(x)/4 (there is no upper semicomputable function f(i) such that |f(i)

[35]

(a) Prove that the function βx(i) is not upper semicomputable to within precision l(x)/4 (there is no upper semicomputable function f(i) such that |f(i) − βx(i)| ≤ l(x)/4).

(b) Prove that there is no algorithm that for every n and every x of length n upper semicomputes a nonincreasing function that follows the shape of βx with small error, in the sense of Definition 5.5.8 on page 415.

In particular, there is a function δ(n) = O(log n) with the following property. Let α(n) and (n) be computable natural-valued functions with 2(n) ≤ α(n) ≤ n−2(n)−δ(n) and (n) > δ(n). Then, there is no upper semicomputable function

f, given x, such that for every n and every x of length n, we have βx(α(n)) < f(α(n)) < βx(α(n) − (n)) + (n).

Comments. Item

(a) improves Exercise 5.5.17, Item (e). Item

(b) resolves part of an open problem in [N.K. Vereshchagin and P.M.B. Vit´anyi, Ibid.]. Source: [M.A. Ustinov Proc. Int. Comput. Sci. Symp. Russia

(CSR), Lect. Notes Comput. Sci., Vol. 3967, Springer-Verlag, 2006, 364–

368].