What can we say a language is recursively enumerable if it can be simulated?

Question

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.

Answer 1

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.