0
$\begingroup$

Consider the language $L = \{\langle M \rangle: \text{ $M$ accepts at most two single-letter words}\}$, where $\langle M\rangle$ is the encoding of Turing machine $M$.

We need to determine, without using Rice's Theorem, whether:

  1. $L\in \text{R}$, i.e., $L$ is decidable.
  2. $L \in \text{RE}\setminus \text{R}$, i.e., $L$ is semi-decidable but not decidable
  3. $L \notin \text{RE}$, i.e., $L$ is not semi-decidable.

Any hints or some steps on how to approach this problem would be appreciated.

Also, if $L\notin \text{R}$, can we prove that using Rice's Theorem?

$\endgroup$
1
  • $\begingroup$ There is one way to think about it. If we could build a Turing machine that semi decides this language L. Then given <M> in L we could be able to find out if M accepts at most 2 strings which seems logically impossible as we will never be able to determine that. So this seems to be not SemiDecidable. But the argument above is logical but not formal proof. Don't know how to extend it to a formal proof $\endgroup$ – Ronit sharma Dec 3 '20 at 15:07
0
$\begingroup$

The language $L$ is not in $\text{RE}$. Consider the complement of the halting problem $\overline{Halt_{TM}} = \{ \langle M, w\rangle: \text{ $M$ does not halt on $w$}\}$ which is not in $\text{RE}$. We show that $\overline{Halt_{TM}}$ reduces to $L$ (and therefore, $L \notin \text{RE}$). From this point, I am assuming w.l.o.g that every machine has an input alphabet that contains at least three letters $a, b, $ and $c$.

A mapping reduction from $\overline{Halt_{TM}}$ to $L$ operates as follows. On input $\langle M, w\rangle$ of the reduction, the reduction outputs $\langle K\rangle$, where $K$ is a machine that operates as follows. On input $x$ of $K$, if $x = a$ or $x = b$, $K$ accepts. Otherwise, if $x\notin \{ a, b\}$, then $K$ simulates the run of $M$ on $w$. If $M$ halts on $w$, then $K$ accepts $x$. The reduction is correct. Indeed, if $M$ does not halt on $w$, then $K$ accepts the inputs $x = a$, and $x = b$, and does not halt on any other input. In particular, $K$ accepts at most two single-letter words. Conversely, if $M$ Halts on $w$, then $K$ accepts all inputs $x$, in particular, $K$ accepts at least three single letter words $a, b,$ and $c$.

Since $\text{R}\subseteq \text{RE}$, the above also proves that $L$ is not decidable. Yet, if you want to prove that $L$ is not decidable using Rice's theorem, then you note that the property $\text{P} = \{ M: \text{ $M$ accepts at most two single-letter words} \}$ is a non-trivial semantic property:

  1. $\text{P}$ is nontrivial: it is easy to show that there are machines that accept at most two single-letter words, and there are machines that accept at least three single-letter words. I leave the details to you.

  2. $\text{P}$ is semantic: let $M_1$ and $M_2$ be two machines with $L(M_1) = L(M_2)$. We need to show that both $M_1$ and $M_2$ are in $\text{P}$, or both are not in $\text{P}$. This is also easy as $M_1$ and $M_1$ recognise the same language, in particular, they accept the same single-letter words.

$\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.