[30] Show that the following statements are equivalent for an infinite binary sequence : There exists a c such that for infinitely many n, possibly

[30] Show that the following statements are equivalent for an infinite binary sequence ω: There exists a c such that for infinitely many n, possibly different in each statement, C(ω1:n|n) ≤ c, C(ω1:n; n) ≤ l(n) + c, C(ω1:n) ≤ l(n) + c.

The sequences thus defined are called pararecursive sequences.

(b) Show that no pararecursive sequence satisfies the condition of Theorem 2.5.6.

Comments. In modern terminology ‘pararecursive’ should be ‘paracomputable.’ Comparison with the other exercises shows that the computable sequences are contained in the pararecursive sequences. It also shows that the pararecursive sequences have the cardinality of the continuum, so this containment is proper. R.P. Daley [J. Symb. Logic, 41(1976), 626–638] has shown that the characteristic sequences of computably enumerable sets are pararecursive, and containment in the set of pararecursive sequences is proper by the same argument as before.

Hint for Item (b): use Theorem 2.5.5.

But for every unbounded function

f, there is a pararecursive sequence ω such that for infinitely many n we have C(ω1:n|n) ≥ n − f(n); see Exercise 2.5.8 on page 161. Source:

[H.P. Katseff and M. Sipser, Theoret. Comput. Sci., 15(1981), 291–309].