0

For example, consider the language $L$ given by

$$L = \{ M : M \; \textsf{halts on} \; \epsilon \}$$

I understand why this language is not recursive, but how do we prove it is recursively enumerable? I spoke with a friend, and he simply said M($\epsilon$) can be simulated, so we know it is recursively enumerable.

Evangelos Bampas
  • 669
Ralff
  • 1,487

1 Answers1

2

To show that $L$ is recursively enumerable, we just need to construct a Turing Machine $N$ that receives as input the encoding of a Turing machine $M$, with the following specification:

  • If $M$ accepts $\epsilon$, then $N$ must accept $M$.
  • Otherwise, $N$ can reject or loop forever.

We construct $N$ so that it simulates $M$ on input $\epsilon$. If $M$ ever terminates, $N$ gives the same answer as $M$. Note that this respects the specification above.

The only thing we need to do is to simulate $M(\epsilon)$. This is what your friend meant when he said that we know it is recursively enumerable because $M(\epsilon)$ can be simulated.

Evangelos Bampas
  • 669
  • Thanks. I think I understand. So, the complement of L (M does not halt on the empty string) is not recursively enumerable because the simulation for the complement of L would never accept because it would run forever. – Ralff Mar 08 '17 at 17:53
  • @cBEiN Yes. For $\overline{L}$, you will have trouble accepting the machines that do not terminate on $\epsilon$. – Evangelos Bampas Mar 09 '17 at 07:44