Turing Machine recognizability

Question

I'm trying to go over some review problems regarding Turing Machine recognizability, and am still pretty confused about the following problems. This is the only information we are given in the problem statement.

1. L1 = {hMi : |L(M)| ≤ 10}. Is L1 recognizable? Prove your answer.
2. L2 = {hMi : |L(M)| ≥ 2}. Is L2 recognizable? Prove your answer.
3. L3 = {hMi : |L(M)| = 2}. Is L3 recognizable? Prove your answer.

Any help at all would be so appreciated. Thank you!

Answer 1

I think here $L(M)$ might mean the language of machine $M$, i.e. the sets of words on which the machine accepts. I will work assuming this is the case.

1. Assume L1 is recognizable. I'll show this implies halting problem is decidable. Indeed, halting problem is recognizable, so we only need to show that complement of halting problem is recognizable. Let A1,A2,...,A10,A11 be any 10 words in the machine's alphabet. Now let's take any machine N, halting of which we want to decide. Let M be a machine which on any word different from Ai halts immediately, and on any word Ai simulates N on empty input, and if N halts, then it accepts the word. Now, as L1 is recognizable (we assume this!) we will be able to recognize when N doesn't halt. So complement of halting problem is recognizable, which means halting problem is decidable, contradiction.

2. L2 is recognizable - If w1,w2,w3,... is enumeration of all words over machine's alphabet, then first we simulate 1 step of M on w1, then 2 steps on w1 and w2, then 3 steps on w1, w2 and w3 etc. and count on how many of these words M halts. As soon as we find 2 words on which M halts, we accept.

3. L3 is not recognizable, by argument similar to one for L1, with the following differences: we have just 3 words, A1 A2 and A3, and M will always accept A1 and A2, and accept A3 iff N halts on empty input.