[O39] It is unknown whether there is an algorithm that, for every x, lower semicomputes a nonincreasing function f(i) that follows the shape of x(i)

[O39] It is unknown whether there is an algorithm that, for every x, lower semicomputes a nonincreasing function f(i) that follows the shape of βx(i) with error O(log n) (or even o(n)), in the sense of Definition 5.5.8 on page 415.

Comments. The analogous question concerning upper semicomputability is settled in Exercise 5.5.18, Item (b). Source: [N.K. Vereshchagin and P.M.B. Vit´anyi, IEEE Trans. Inform. Theory, 50:12(2004), 3265–3290].