2
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\begingroup$ Buzzword: extended Rice's theorem. $\endgroup$ – Raphael Nov 2 '15 at 19:46
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Sherlocked! $\hspace{0pt}$ $\endgroup$ – Raphael Nov 2 '15 at 19:53
  • $\begingroup$ I get your point thanks. I understand the given a Turing machine the ability to build an enumerator that prints strings recognized by the Turing machine in order would give us the power to make a decider for the language which I know is not possible. But the implication of decidability by semi-decidability in this case would only hold for Turing machines which recognize languages that have infinite many strings . Am I correct about that ? $\endgroup$ – sashas Nov 2 '15 at 22:23
  • 1
    $\begingroup$ @sasha Yea, kind of. But that's okay: all finite languages are decidable, anyway. ;) $\endgroup$ – Raphael Nov 2 '15 at 22:40
4
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.