1
$\begingroup$

$$L = \{ \langle M \rangle \mid \text{\(M\) is a Turing Machine and \(|L(M)| = 1\)} \}$$

I have to prove that this is not R.E. and not co-R.E.

I know how to approach these kind of problems. For $\check L = \{ \langle M \rangle \mid \text{\(M\) is a Turing Machine and \(|L(M)| \le 1\)} \}$, Here a simple reduction from complement of HP would do the trick. (Make a TM $M'$ which on input $w$ runs $M$ on $x$ and accepts if $M$ accepts $x$. If $\langle M,x \rangle$ belongs to complement of HP then $x$ would not be accepted and hence $M'$ would reject everything thereby satisfying the $\le 1$ property. Also in case $\langle M,x \rangle$ doesn't belong to complement of HP, $M'$ would accept everything and hence would be $\gt 1$. Thus we know that the complement of HP is reducible to $\check L$. Hence $\check L$ is not RE.)

But in the main problem I don't have an inequality and I am stuck with how to approach such problems. I would face the same problem while proving $L'$ (complement of $L$) as not RE for proving $L$ as not co RE.

$\endgroup$
  • $\begingroup$ See also here. $\endgroup$ – Raphael Mar 10 '16 at 15:09
1
$\begingroup$

One way to solve this problem is by showing there do not exist Turing machines that accept $L_3$ or $\overline L$. But probably that is simply restating the question.

$L_u$, the universal language, is non-recursive but RE language. If we reduce $L_u \leq_M L$ then $L$ cannot be co-RE. If we reduce $L_u \leq_M \overline{L}$ then $L$ cannot be RE.

Let us first do the reduction $L_u \leq_M L$.

We shall reduce $\langle M,w\rangle$ to a Turing machine $M'$ as follows: $M'$ rejects all inputs other than $w$. If the input is $w$ then it runs as Turing Machine $M$ on $w$. This gives us $\langle M,w\rangle \in L_u$ iff $M' = f(\langle M,w\rangle) \in L$.

Hence $L_u \leq_M L$. Therefore $L$ cannot be co-RE. Otherwise $L_u$ will become recursive.

Next we do the reduction $L_u \leq_M \overline L$.

We shall reduce $\langle M,w\rangle$ to a Turing machine $M''$ as follows: Let $w'$ be a string other than $w$. $M''$ rejects all inputs other than $w$ and $w'$. If the input in $w'$ then $M''$ accepts the input. If the input is $w$ then it runs as Turing Machine $M$ on $w$. This gives us $\langle M,w\rangle \in L_u$ iff $M''= f(\langle M,w\rangle) \not\in L$, that is, $\langle M,w\rangle \in L_u$ iff $M'' \in \overline L$.

Hence $L_u \leq_M \overline{L}$. Therefore $L$ cannot be RE. Otherwise $L_u$ will become recursive.

If we combine the results, $L$ is neither RE nor co-RE.

$\endgroup$
  • $\begingroup$ How do we make sure that our TM rejects "all inputs other than w"? Isn't w a general representation of an input and not the input itself? $\endgroup$ – ajaatshatru Mar 11 '16 at 3:58
  • $\begingroup$ Also if I wish to prove for |L(M)| = 2, would it be correct to follow the same approach and accept only two inputs and reject everything else? Thanks for helping out! $\endgroup$ – ajaatshatru Mar 11 '16 at 4:00
  • $\begingroup$ Yeh, sure, for any |L(M)| = k. $\endgroup$ – Shreesh Mar 11 '16 at 11:21
  • $\begingroup$ I misread the Theorem stating that if A ≤ B then if B is Turing Recognizable, A is too. I read it the other way round and was thus stuck with this. Thanks a lot! $\endgroup$ – ajaatshatru Mar 11 '16 at 21:01

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.