# Difference between a TM with an empty language and the one accepting empty string

If a TM(Turing Machine) accepts NO input string(even the blank), then its language is empty.

If a TM ONLY accepts the blank string(meaning that there is nothing on the tape except for the default blank characters), then its language has only one item and it is the blank string.

Are these definitions correct?

Could you describe the TM for each?

Also, this might be irrelevant but let me ask: I saw somewhere that there must be at least two states for a TM. Which states must be there all the time in a TM?

• A student once called $\{\varepsilon\}$ the "almost empty" language. I guess $\{\emptyset\}$ would be the "almost empty" set. – Raphael Apr 3 '13 at 20:55
• @Raphael Isn't language also a set? – msn Apr 9 '13 at 12:24

The definitions (well, descriptions) look correct, more or less.

A TM accepting the empty language may move directly into the halt reject state, regardless of what may or may not be on the input tape.

A TM accepting the language consisting of only the empty string may examine the first tape symbol. If the symbol is a blank, it could move to the halt accept state. Otherwise, it would move to the halt reject state. We don't have to worry about the user providing an input that starts on some later position in the tape since the blank symbol is not allowed in the input alphabet.

To summarize:

A TM for $\{\epsilon\}$ has pseudocode:

if tape[1] is blank then accept else reject


A TM for $\emptyset$ has pseudocode:

reject


or, if it helps you make the difference even clearer:

if tape[1] is blank then reject else reject


As Yuval points out in the comments, there are infinitely many TMs accepting one or the other of these languages; the two suggested here are for illustrative purposes only.