Which one of these two sets is computably enumerable?

Question

M is a turing machine description, L(M) is recognized by M, |L(M)| is the size of this language.

1. {M : |L(M)| <= 330}

2. {M : |L(M)| >= 330}

I don't quite understand what this question is asking. Does the first question mean M accepts at most 330 inputs?

---

My thoughts:

1. co-CE

2. CE (Construct a M to check the input, if >= 330 inputs are accepted, halt)

I am not sure if I am correct, and can I prove the first question is not CE by decribing TM may never halt?

Answer 1

As Rick commented, the first question is asking whether the set of Turing machines that recognize no more 330 strings is computably enumerable. Similarly, the second question is asking whether the set of Turing machines that recognize no less 330 strings is computably enumerable.

Let us show that second set is computably enumerable using dovetailing. Let $M_1, M_2, \cdots$ list all Turing machines. Let $w_1, w_2,\cdots$ list all words over the alphabet. We can build a Turing machine using the universal Turing machine to run the following procedure.

• for i from 1 to infinity:
  • for j from 1 to i:
    • let string_count be 0
    • for k from 1 to i:
      • run $M_j$ with input $w_k$ up to $i$ steps. If it is found $M_j$ accepts $w_k$, add 1 to the string_count. If string_count is no less than 330, append $M_j$ to the output tape.

It is clear that every Turing machine that accepts no less than 330 strings will be added to the list at some point of time. Although each of them may be listed many times, that does not matter. Also only that kind of machines will be included in the list. So we have shown that the second set is computably enumerable.

Rice's theorem tells us the second set, which is $$\{\langle M\rangle : M\text{ is a TM and }L(M)\text{ has property that its size is no less than } 330 \}$$ is undecidable. Since it is computably enumerable, its complement (relative to the decidable problem whether a string encodes a Turing machine) $$\{\langle M\rangle : M\text{ is a TM and }L(M)\text{ has property that its size is less than } 330 \}$$ cannot be computably enumerable. Well, the size of that number 330 does not affect our argument here. If we change it to 331, we see that the first set is not computably enumerable.