2
$\begingroup$

I TA for a course in theory of computation and this came up as an interesting question.

$E_{TM}$ is the set of TM descriptions where the machine's language is empty.

Of course, $E_{TM}$ is undecidable for arbitrary TMs (as well as $A_{TM}$).

Now suppose we restrict our attention to decider TMs (ones that always halt).

$A_{decider}$ is the set of TM decider descriptions and strings such that the TM accepts that string, and $E_{decider}$ is the same as $E_{TM}$ except for deciders.

Of course, $A_{decider}$ now is decidable because we just simulate the decider on the input, and it will always stop.

Is $E_{decider}$ decidable now, or does it remain undecidable? The reduction to show that $E_{TM}$ was undecidable originally goes in the wrong direction here.

$\endgroup$
  • $\begingroup$ I think that you want to study separability rather than decidability. The point is, you can't write a TM accepting $A_{decider}$ and rejecting its complement, since its complement contains descriptions of non-deciders as well! You want a TM which accepts $A_{decider}$ and reject the set $B$ of pairs (decider,string) where the decider rejects the strings. On pairs (nondecider,string), you do not care about accepting/rejecting, or even terminating. This notion is called separability of $A_{decider}$ and $B$. $\endgroup$ – chi May 12 '18 at 12:55
1
$\begingroup$

$E_{decider}$ is even unrecognizable.

Suppose a TM $E$ recognizes $E_{decider}$, we construct a TM $N$ recognizing $\overline{H}=\{\langle\langle M\rangle, w\rangle\mid M(w) \text{ doesn't halt}\}$, which is known as unrecognizable, thus a contradiction. $N$ works as follows.

On input $\langle\langle M\rangle, w\rangle$:

  1. Construct a TM $M_w$ working on input $x$ as follows

    1. Run $M$ on $w$ with at most $|x|$ steps.
    2. If $M$ halts, loop; otherwise, reject.
  2. Run $E$ on $\langle M_w\rangle$.

  3. If $E$ accepts, accept; otherwise, reject.

If $M$ halts on $w$, then there exists some $x$ such that $M_w$ does not halt on $x$, which means $M_w$ is not a decider. Therefore $E$ does not accept $M_w$, so $N$ does not accept $\langle\langle M\rangle, w\rangle$.

If $M$ does not halt on $w$, then $M_w$ halts and reject any string $x$. Therefore $E$ accepts $M_w$, so $N$ accepts $\langle\langle M\rangle, w\rangle$.

Now the proof is complete.


In addition, your argument about $A_{decider}$ is wrong, because the TM in input may not be a decider and you should reject (not loop) on such case. In fact, you can prove $A_{decider}$ is also unrecognizable using similar technique.

$\endgroup$
  • $\begingroup$ This isn't the same language, it's somewhat like a promise problem in that I guarantee that the input TM will be a decider. $\endgroup$ – Ryan Apr 13 '18 at 13:56
  • $\begingroup$ @Ryan My answer perfectly matches the question in OP. If you wrongly described the question, you can ask a new question. $\endgroup$ – xskxzr Apr 13 '18 at 14:04

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.