1
$\begingroup$

Suppose $B_{TM}$ = $\{ \langle M \rangle$ | $M$ is a Turing machine over $\{0, 1\}$ and $M$ accepts $\epsilon\}$.

I do not understand what it means for $M$ to accept $\epsilon$. Can someone explain what this language $B_{TM}$ consists of and what is $\epsilon$?

$\endgroup$

1 Answer 1

2
$\begingroup$

$\epsilon$ is the empty string. A Turing machine accepts $\epsilon$ if the start state of its finite control is an accepting state.

$\langle M\rangle$ is a "description" of a Turing machine $M$. One way to think of it is to think of any reasonable method for writing down Turing machines and then to imagine $M$ as a string written down in this way. Another way to think of it is that every possible Turing machine has been enumerated and listed in a big book somewhere, and then $\langle M\rangle$ is the number for the appearance of $M$ in the book, with $\langle 1\rangle$ being the first one on the first page, and so on.

$B_{TM}$ here is the set of strings $S$ such that $S$ describes a Turing machine $M$—that is, such that $S=\langle M\rangle$—and $M$ halts on $\epsilon$.

$\endgroup$
2
  • $\begingroup$ Exactly what I was looking for, just didnt know what $\epsilon$ was. I just have one concern, would the length of $\epsilon$ be 0 then? $\endgroup$ Commented Feb 8, 2014 at 22:38
  • $\begingroup$ Yes, $\epsilon$ is the unique string of length 0. $\endgroup$
    – MJD
    Commented Feb 9, 2014 at 3:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .