Let $L = E_{TM} = \left\{ \left<M \right> | M \text{ is a TM and L(M)} = \emptyset \right\}$.

Does $L$ accepts the empty word $\varepsilon$?

In other words, is $$\varepsilon \in L$$

I'm a little bit confused by this.

My intuition says it doesn't since the empty set rejects every input.

  • 2
    $\begingroup$ The answer depends on how you encode Turing machines. Which Turing machine does the empty string represent, if any? $\endgroup$ – Yuval Filmus Apr 7 '19 at 6:35
  • $\begingroup$ I think it would be reasonable to assume that no Turing machine has the empty string as a representation. $\endgroup$ – Pål GD Apr 7 '19 at 7:29
  • $\begingroup$ @PålGD Sometimes we would prefer that any string represent some Turing machine. $\endgroup$ – Yuval Filmus Apr 7 '19 at 9:07

I would answer that no, $\varepsilon \notin L$.

The reason is that the typical definition of a Turing machine is that its representation should contain a non-empty set of states and a non-empty tape alphabet.

In order to represent those, you typically would need a non-empty string.

However, as Yuval points out, you are free to define your own Turing Machine description language, and if you were to say "We use $\varepsilon$ to denote the "empty" TM (with alphabet 0), the TM that runs forever", you are free to do so, in which the answer becomes Yes.

I would go with No, $\varepsilon \notin E_{TM}$.

| cite | improve this answer | |

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.