Is the language of all deciders recognizing empty language decidable?

Question

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.

Answer 1

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