[Solved]: Is the language TMs that accept finite languages Turing-recognizable?

Problem Detail: 

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 ?

Asked By : sashas

Answered By : Raphael

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49000