[20] Define the state complexity S(x) of a finite binary string x as the least n such that there is a Turing machine with n states that started in the standard initial conditions of empty tape and distinguished start state will eventually halt with x on its output tape. All machines considered are of the original model as in Section 1.7. Define B = {x, y :

S(x) ≤ y}.

(a) Prove that B is computably enumerable but not computable.

(b) Prove that B is Turing complete (in the sense of Exercise 1.7.16).

Comments. Suppose our Turing machines use an m-letter alphabet. Let Tm(x) denote the complexity of x in terms of the minimal number of internal states of a Turing machine. Then Tm(x) ∼ C(x)/ (m − 1) log C(x).

Source: problem by J. Andrews [electronic news, June 24, 1988]; solutions by V.R. Pratt and independently R.M. Solovay [electronic news, June 1988].