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

Problem Detail: 

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?

Asked By : msn

Answered By : Patrick87

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.

[EDIT]Some additional discussion motivated by recent comments.

(1) Depending on what your definition of a TM is and/or how explicit you want to be, there are two possibilities. If you want your machine to explicitly enter a halting state for every input tape, then yes, you will have a transition to the halt reject state on every symbol of the input alphabet. If you allow your Turing machine to reject strings by "crashing" (reaching a configuration for which there is no defined transition), then these transitions aren't necessary; simply transition to halt accept on blank, and let the machine crash in all other cases.

(2) Yes, the machine which accepts the empty language always rejects. Notice that it is perfectly acceptable to define automata with accepting states which are never reached (depending upon your definition, of course). In particular, we could take any arbitrary TM and change it to accept the empty language by changing all transitions from the initial state to lead to the halt reject state.

(3) Typically, TMs are understood to have two special states in addition to any "user-defined" states: the halt accept and halt reject states, which the TM enters to explicitly accept or reject, respectively, some input. In addition to these two states, an initial state is required from which to begin processing the input. By my reckoning, this means that every TM has at least three states. Notice, though, that not all of these states needs to be used by any given TM. In particular, a valid TM might endlessly loop on the initial state for all inputs; this TM will accept the empty language (although it doesn't decide it; to decide it, it needs to enter one of the halting states for each input).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10996