# Is the language of all deciders recognizing empty language decidable?

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.

• 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$. – chi May 12 '18 at 12:55

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

• 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. – Ryan Apr 13 '18 at 13:56
• @Ryan My answer perfectly matches the question in OP. If you wrongly described the question, you can ask a new question. – xskxzr Apr 13 '18 at 14:04