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

ignougroup
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 Mrangle$ 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 Mrangle$ (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