Is the language TMs that accept finite languages Turing-recognizable?

Question

I know that $L=\{ \langle M \rangle \mid |L(M)| < \infty \}$ is not decidable (by Rice's theorem or using reduction, I followed it from $L$ not being decidable ). But is $L$ recognizable?

What I tried is, let $L$ have a machine that recognizes it, let it be called $H$. Then given an input $\langle M\rangle$ I would start enumerating all strings in $L$ by using $H$. As $L$ has infinite many strings at some point the string being enumerated will be equal or larger than $\langle M\rangle$ (in lexicological order), thus using $H$ I am able to decide $L$ which I know is not possible.

Is my method correct ? In either case is there a better method for example is there a general way for proving that a language is not recognizable like for undecidability we try to reduce an undecidable problem to the current problem ?

Answer 1

If that method worked, semi-decidability would always imply decidability for infinite languages (note how you don't need any property of $L$ to make the proof work), which we know is not true.

Since your reasoning is sound, one of your assumptions has to be faulty. What you assume is, paraphrased:

Assuming semi-decider $H$ for $L$, I can enumerate $L$ in lexicological order by using $H$.

You don't say how you do this, though, and we have already determined that you can not.

What you probably had in mind that we always get a recursive enumerator, and even a repetition-free one for infinite languages. Thus, it's the order that has to be impossible to achieve.

Intuitively, you can not reject $i$ as next output of the enumerator after only finite time.

---

Proving that $L$ is not semi-decidable works by reduction as well. See here for inspiration.

Hint:

Reduce from $\overline{K}$, the complement of the Halting language.

Details:

Define a computable mapping $\langle M \rangle \mapsto \langle M' \rangle$ so that $\langle M \rangle \in \overline{K}$ if and only if $\langle M' \rangle \in L$. For instance, define $M'$ by

 M'(y) :
   Simulate M(⟨M⟩) for y steps.
   if M halts
     accept y
   else
     reject y

Note how $L(M') = \emptyset$ if $\langle M \rangle \in \overline{K}$, and $L(M') = \mathbb{N}_{\geq N}$ if $M$ halts after $N$ steps on its own code.

Answer 2

I don't believe the method you're proposing works. While you will eventually enumerate a string that comes after $\langle M \rangle$, that doesn't mean that $L$ is decidable.

However, you can use an enumerator for $L$ and the recursion theorem to show that this language is not recognizable. Here's a proof sketch. Suppose $L$ is recognizable. Let $E$ be an enumerator for it. Now, design a machine $M$ that gets its own description, then runs the enumerator. If it ever sees its own description, it immediately accepts its input. Otherwise, it loops forever.

Now, if $\langle M \rangle \in L$, then $M$ will eventually see $E$ list its description, so it will always accept, meaning that it has an infinite language, a contradiction. Otherwise, the enumerator will never list $\langle M \rangle$, so it never accepts anything, but then its language is finite, a contradiction!