[35] Use the definitions given earlier. The following is known as Post’s problem (1944). The computable sets have lower r-degree of unsolvability than K0, which has the highest r-degree of unsolvability in the computably enumerable sets. Are there other r-degrees of unsolvability (all r = 1, m, T )? For r = 1, m, the first examples of such sets were the simple sets of Exercise 1.7.16; see Item

(c) below. (For r = T the question is much harder, and the affirmative answer was provided

(independently) by R.A. Friedberg and A.A. Muchnik only in 1956.)

(a) Show that for all A, A is m-complete iff A is 1-complete.

(b) Show that {x : φx is total} and {x : φx is not total} are incomparable under ≤m. (Hint: see Exercise 7-11 in H. Rogers, Jr., Ibid.)

(c) Show that a simple set is neither computable nor m-complete.

(d) Show that ≡1 and ≡m do not coincide on the incomputable computably enumerable sets, and hence ≤1 and ≤m do not coincide on these sets either.

(e) (J.C.E. Dekker) Show that the m-degree of a simple set includes an infinite collection of distinct 1-degrees consisting entirely of simple sets.
Comments. From Item

(c) it follows that there exist incomputable computably enumerable sets (simple sets) that are not m-complete (and so by Item

(a) not 1-complete). Source: [H. Rogers, Jr., Ibid.]. The term ‘Post’s problem’ is now used among computability theorists only for the Turing reduction version.