Suppose that L is decidable. Is L+ decidable?
Determine which of the following sets are computably enumerable and which
are not computably enumerable:
(a) {(ψ(M1ψ(N) : M takes fewer steps than N on input ε}.
(b) {ψ(M) : M takes fewer than 20092009 steps on some input}.
(c) {ψ(M) : M takes fewer than 20092009 steps on at least 20092009 different
inputs}.
(d) {ψ(M) : M takes fewer than 20092009 steps on all inputs}.
(e) {ψ(M) : M accepts at least 2009 strings}.
(f) {ψ(M) : M accepts at most 2009 strings}.
(g) Complement of {ψ(M) : M accepts at least 2009 strings}.
(h) Complement of {ψ(M) : M accepts at most 2009 strings}.
(i) {ψ(M) : L(M) contains at least 2009 strings}.
(j) {ψ(M) : L(M) contains at most 2009 strings}.
(k) {ψ(M) : M halts on all inputs of length less than 2009}.
(l) Complement of {ψ(M) : M halts on all inputs of length less than 2009}.