4
$\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.

Improve this question
$\endgroup$
3
  • $\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
    Commented Feb 5, 2017 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
    Commented Feb 5, 2017 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
    Commented Feb 5, 2017 at 13:32

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$

Your Answer

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

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