6
$\begingroup$

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?

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

1 Answer 1

8
$\begingroup$

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).

$\endgroup$
5
  • 2
    $\begingroup$ While the two Turing machines decide the advertised languages, there are infinitely many Turing machines for these languages. A Turing machine accepting the empty language can start by searching for a proof of Fermat's last theorem, and then go into the reject state. It could even check whether its input is prime, and then go into the reject state. $\endgroup$ Apr 3, 2013 at 18:44
  • $\begingroup$ @YuvalFilmus Good point; I use "a" correctly, but somewhat confusingly use "will" instead of "may". Editing the answer to make it clear that these represent one option. $\endgroup$
    – Patrick87
    Apr 3, 2013 at 18:49
  • $\begingroup$ This is a good answer but still I want to be sure, so let me ask these: 1) In checking for the language to see if it accepts empty string, we check the first square of the tape as you said and if blanck we accept. You said otherwise we reject. To check this otherwise, are we going to check for all the alphabet in the Sigma(the set of input alphabet) for this? 2) For the definition of the machine with empty language, can we say "Whether or not there is an Accept state the machine will always Reject"? 3) Please answer the last part of my question too (the states of a TM) $\endgroup$
    – Mahdi
    Apr 9, 2013 at 12:43
  • $\begingroup$ Thanks for the extra information. Let me ask this too: There are 3 q's in the definition of a TM(q0, qAcc, qRej). As you said these cannot be empty but we do not have to use them(while they are there in the definition). So as you said we can have a TM which crashes(loops) in every input in the state q0. In this case, what are going to be the transitions from q0 to qAcc and qRej? Or is it ok if we have 3 states in our state chart without any transitions among them? $\endgroup$
    – Mahdi
    Apr 13, 2013 at 13:03
  • 1
    $\begingroup$ @mahdisaeedi It's perfectly fine to have unreachable states in an automaton. If you really want your graph to be fully connected, though, you can add a special symbol to your tape (not input!) alphabet. Then, add a transition on reading this symbol from the start state to every other state. You now have a nondeterministic TM with all states reachable (in the graph theory sense) which accepts precisely the same language as before (nondeterministic TMs are not stronger than deterministic ones, either). $\endgroup$
    – Patrick87
    Apr 14, 2013 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.