[39] Prove that there is a computably enumerable set A with characteristic sequence such that for every total computable majorant of C and

[39] Prove that there is a computably enumerable set A with characteristic sequence χ such that for every total computable majorant

φ of C and every n, we have φ(χ1:n|n) ≥ cφn, where cφ is a constant independent of n (but dependent on φ).

Comments. Use the proof of Theorem 7.1.3 and also Example 4.1.1.

Source: [A.K. Zvonkin and L.A. Levin, Russ. Math. Surveys, 25:6(1970), 83–124], attributed to J.M. Barzdins and N.V. Petri. See also Example 4.1.1.