[25] Kolmogorov complexity arguments may be used to replace diagonalization in computational complexity. Prove the following using Kolmogorov complexity:

(a) If limn→∞ s(n)/s

(n) → 0, and s

(n) ≥ log n computable in space s

(n), then DSPACE[s

(n)] − DSPACE[s(n)] = ∅.

(b) If limn→∞ s(n)/s

(n) → 0, with s

(n) computable in space s

(n) and s

(n) ≥ 3n, then there is a language L ∈ DSPACE[s

(n)] such that L is DSPACE[s(n)]-immune.

(c) Let r(n) be a total computable function. There exists a computable language L such that for every Turing machine Ti accepting L in space Si(n), there exists a Turing machine Tj accepting L in space Sj (n) such that r(Sj (n)) ≤ Si(n), for almost all n.

(d) Exhibit a Turing machine that accepts an infinite set containing no infinite regular set.

Comments. Source: suggested by B.K. Natarajan. In Item

(a) we consider the DSPACE hierarchy. The original space hierarchy theorem was studied by R. Stearns, J. Hartmanis, and P. Lewis II [6th IEEE Symp.

Switching Circuit Theory and Logical Design, 1965, pp. 179–190]. Item

(c) is the Blum speedup theorem from [M. Blum, J. Assoc. Comp. Mach., 14:2(1967), 322–336].