Theory of Computation

2.10 COMPLETENESS

The concept of reducibility has been instrumental toward certifying in the preceding papes that several problems were unsolvable or non c.e. culminating to the proof of Rice’s lemmata and theorem. At the heart of the use of the technique was the observation that when A ≤_m B or A ≤₁ B, then B is “more unsolvable” than A. Does this ordering, ≤,_m (resp. ≤₁), have a “maximal” element among c.e. sets? Indeed, it does have several. Such sets are called m-complete (resp. 1-complete).

2.10.0.9 Definition. (m- and 1-completeness) A set A is called m-complete (resp. 1-complete) if the two conditions below hold

(1) A is c.e.

(2) If S is any c.e. set, then S ≤_m A (resp. S ≤₁ A).          □

2.10.0.10 Example. K₁ = {[x, y] : _x(y) ↓} is 1-complete.

Indeed, first K₁ is semi-recursive since

z K₁ ≡ (∃y)(∃y)(z = [x, y] ∧ _x(y) ↓)

Second, let S be c.e., that is, S = W_e for some e. Then x S ≡ [e, x] K₁. Thus, S ≤₁ K₁, since x.[e, x] is 1-1.          □

2.10.0.11 Example. K 1-complete. Indeed, ...