3
$\begingroup$

I have some questions regarding the emptiness problem of Turing machines when we have a TM which accepts empty language, and we have to make sure that the TM does not accept any string. My questions are:

  • in formal description of TM I have read that input alphabet can't be empty then how a machine can accept empty input?
  • if we have a machine which accepts empty string then "how is it undecidable?" When we can simply reject any non-empty string?

If I got some concepts wrong or messed it up, kindly correct me.

$\endgroup$
  • $\begingroup$ Your question is a bit unclear. Also, I think you're confusing between two languages, $A = \{\}$ and $B = \{\langle M \rangle \mid L(M) = \{\}\}$ One is the empty set and the other is the set of all Turing machines that accept the empty set. $\endgroup$ – skankhunt42 Feb 5 '17 at 7:59
  • $\begingroup$ yup i'm confused between these two, if an empty set is not accepted by a machine then how can there exit a set of all Turing machines that accept empty set $\endgroup$ – Iqra Rana Feb 5 '17 at 8:56
  • $\begingroup$ @IqraRana The empty set is accepted by every machine that rejects everything. (It rejects everything, so what strings does it accept? None -- the set of accepted strings is empty, i.e., it accepts the empty set.) $\endgroup$ – David Richerby Feb 5 '17 at 13:32
4
$\begingroup$

You are confused on several accounts. The language of a Turing machine $T$ consists of all inputs $x$ such that when $T$ runs on $x$, it terminates in an accepting state. (There are several other equivalent definitions.) In particular, the language of a Turing machine can be empty no matter what the alphabet is. All it has to do is never terminate in an accepting state.

You are confusing the empty alphabet (which doesn't exist - we always require the alphabet to be non-empty), the empty string (which is the unique string of length 0), and the empty language (which contains no strings). In particular, the language consisting of the empty string isn't empty, since it contains the empty string.

The emptiness problem asks to decide, given a Turing machine $T$, whether the language of $T$ is empty or not. All you are given is the Turing machine itself. You aren't given "hints" like in your example. You can prove that the emptiness problem is undecidable. Indeed, it is even undecidable whether a given Turing machine accepts the empty string (we don't care about any other input).

$\endgroup$

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.