I'm having trouble convincing myself of the proof for the following theorem:

$E_{TM} = \{\langle M\rangle\mid M$ is a TM and $L(M) = \emptyset\}$ is undecidable.

I think I understand why we reduce $A_{TM}$ to this problem, where $A_{TM} = \{\langle M, w\rangle\mid M$ is a TM and $M$ accepts $w\}$, but here is where I get lost. We create a modified TM $M_1$ such that:

$M_1=$ "On input $x$:

  1. If $x\neq w$, reject.
  2. If $x = w$, run $M$ on input $w$ and accept if $M$ does."

and consequently create a TM $S$ that decides $A_{TM}$:

$S=$ "On input $\langle M, w\rangle$, an encoding of a TM $M$ and a string $w$:

  1. Use the description of $M$ and $w$ to construct the TM $M_1$ just described.
  2. Run $R$ on input $\langle M_1\rangle$.
  3. If $R$ accepts, reject; if $R$ rejects, accept."

My issue here lies with line 3 of TM $S$. If $R$ accepted, then we must have had $x = w$ and $L(M) = \emptyset$, and $S$ would have rejected. Likewise, if $R$ rejected, then we must have had $x\neq w$ (where $x$ could be any string but $w$). Yet $S$ would accept this, even though the 'goal' for $S$ was to accept string $w$. Can someone show me how to think about this correctly? It would be very much appreciated.

  • 1
    $\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$
    – Raphael
    Mar 1, 2016 at 7:48
  • 1
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael
    Mar 1, 2016 at 7:48
  • $\begingroup$ @Raphael. This is almost entirely non-mathematical pseudocode. I fail to see why LaTeX would be a significant improvement here. $\endgroup$ Sep 27, 2016 at 0:13
  • 1
    $\begingroup$ You haven't specified what $R$ is, leaving us to puzzle out what it is from context. Yes, it's not hard, but it would be better if you simply leveled out that speedbump. $\endgroup$ Sep 27, 2016 at 0:17
  • $\begingroup$ @RickDecker Four of six code blocks are clearly mathematical formulae. $\endgroup$
    – Raphael
    Sep 27, 2016 at 7:23

3 Answers 3


In answer to your question about line 3 of the description of $S$, let's first clarify things a bit: we assume there is a decider, $R$, for $E_{TM}$ and we use this to build a decider, $S$, for $A_{TM}$ (thus eventually establishing that such an $R$ is impossible).

With that out of the way, your question is about what happens when $R$ accepts $\langle M_1\rangle$:

  1. Since $R$ was assumed to be a decider for $E_{TM}$, $R$ accepts $\langle M_1\rangle$ if and only if $L(M_1)=\varnothing$.
  2. From the way $M_1$ was constructed, that can happen only if $M$ doesn't accept $w$ (since $M_1$ rejects everything else),
  3. So $R$ will accept $\langle M_1\rangle$ only if $\langle M, w\rangle\notin A_{TM}$.


  1. $R$ will reject $\langle M_1\rangle$ iff $L(M_1)\ne\varnothing$,
  2. And that can only happen when $M$ accepts $w$,
  3. And hence $R$ will reject $\langle M_1\rangle$ only if $\langle M, w\rangle\in A_{TM}$.

Finally, since $S$ was designed to do the opposite of what $R$ does, we've constructed a decider for $A_{TM}$, which of course is a contradiction, so $E_{TM}$ must be undecidable.


The approach is a little different from usual reduction is because $A_{TM}$, the accepting language, is RE and $E_{TM}$, the empty language, is co-RE.

Therefore we need to reduce $A_{TM}$ instance to $E_{TM}$ instance in such a way that

$\langle M,w \rangle \in A_{TM}$ iff $M_1 \not\in E_{TM}$

We construct $M_1$ from $\langle M,w \rangle$ as follows:

Input: $x$
If $x\neq w$ then reject
else if $x=w$ then Run Universal TM on $\langle M,w \rangle$ and accept if $M$ accepts $w$ (i.e. output the answer of Universal TM).

Step 1 of the Turing Machine $S$ does exactly the reduction from $\langle M,w \rangle$ to $M_1$.

We prove by contradiction that $E_{TM}$ is undecidable. Assume $E_{TM}$ is decidable by a Turing machine $R$. Then we can show that $A_{TM}$ is decidable by reducing an instance $\langle M,w \rangle$ of $A_{TM}$ to instance $M_1$ of $E_{TM}$, get an answer using $R$ on $M_1$ and then flip the answer. But $A_{TM}=L_u$, the universal language, is undecidable. Hence by contradiction $E_{TM}$ is undecidable.

Turing Machine $R$ is used (in OP's description) to tell that if there is a Turing Machine $R$ which decides $E_{TM}$ then we can use it to decide $A_{TM}$. And since we know that $A_{TM}$ is undecidable, surely we can't have such an $R$ and therefore $E_{TM}$ is undecidable too.

Turing machine $S$ (again in OP's description) is a machine that decides $E_{TM}$ if there is an availability of Turing machine $R$ that decides $A_{TM}$ by flipping the answer.

  • 1
    $\begingroup$ I'm sorry, why is this an answer? $\endgroup$
    – Ran G.
    Apr 29, 2016 at 2:37
  • $\begingroup$ We prove by contradiction. Assume $E_{TM}$ is decidable. Then we can show that $A_{TM}$ is decidable by reducing an instance $\langle M,w \rangle$ of $A_{TM}$ to instance $M_1$ of $E_{TM}$, get an answer and then flip it. But $A_{TM} = L_u$, the universal language is undecidable. Hence by contradiction $E_{TM}$ is undecidable. $\endgroup$ Apr 29, 2016 at 13:37
  • $\begingroup$ I don't understand. Can you specify the reduction: what is S (formally), and what is R? Flipping the answer of $A_{TM}$ doesn't necessarily give $E_{TM}$, right? $\endgroup$
    – Ran G.
    Apr 29, 2016 at 13:42
  • $\begingroup$ I used the definition of $S$ given by OP. He is confused by $R$ and has not specified what $R$ is. $R$ is the machine that decides $E_{TM}$ if we assume that $E_{TM}$ is decidable for the sake of contradiction. Step 1 of $S$ is the reduction as given by OP. Step 2 is running $R$ on input $f(x) = M_1$ and Step 3 is flipping the answer. $\endgroup$ Apr 29, 2016 at 13:54
  • $\begingroup$ OK, I missed the OP's notations. It may be helpful if the answer was more self contained. $\endgroup$
    – Ran G.
    Apr 29, 2016 at 14:09

I think the issue might be in the difference between saying "M is the kind of machine that accepts $w$" and "I simulated M on w, and it accepted."

The decider $R$ does not run $M_1$ on any particular input. $R$ just (somehow!) checks whether the language of $M_1$ is empty or not.

We've defined $M_1$ so that its language will be empty if and only if $M$ is a machine that rejects $w$. We did this by having $M^\prime$ reject all strings besides $w$ right away. Then it decides whether to accept $w$ by just copying whatever $M$ does. So, if $M$ rejects $w$, then $M^\prime$ is a machine that rejects everything. If $M$ accepts $w$, then $M^\prime$ is a machine that rejects everything except for $w$.

The machine $R$ is supposed to be able to tell whether a TM is the sort of machine that rejects everything. If that were possible, you could solve the acceptance problem. Given $M$ and $w$, construct the machine $M^\prime$ that copies $M$'s behavior on $w$ and rejects all other strings. Then $M^\prime$ is the type of machine that rejects all strings if and only if $M$ is the type of machine that accepts $w$.

The decider $S$ takes in $M$ and $w$ and produces $M^\prime$. It decides whether $M^\prime$ has an empty language, which immediately tells you whether $M$ rejects $w$. If $M^\prime$ has an empty language, then $M$ rejects $w$, so respond NO—M doesn't accept w. If $M^\prime$ turns out not to have an empty language, we know it has just one string in it— w, and that can only happen if w is in the language of $M$. Respond YES—M accepts $w$.


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.