1
$\begingroup$

$A_{TM}= \{ \langle M,w\rangle \mid M$ is a TM that accepts $w\}$

$E_{TM}= \{ \langle M\rangle \mid L(M) = \emptyset \}$

The standard proof for the undecidability of $E_{TM}$ is given in this question, right?. Doesn't this automatically create a mapping reduction $f$ from $A_{TM}$ to $E_{TM}$ ? Whenever $w \in A_{TM}, f(w) \in E_{TM} $ obviously. The other way: $ f(w) \in E_{TM} \Rightarrow w \in A_{TM} $ seems true, although I suspect that's where the fundamental restriction lies. Can someone clarify this?

The proof given for $A_{TM}$ not being Turing reducible to $E_{TM}$ is the following:

Suppose for a contradiction that $A_{TM}$ $≤_{m}$ $E_{TM}$ via reduction $f$. This means that $w ∈ A_{TM} \iff f(w) ∈ E_{TM} $, which is equivalent to saying $w \notin A_{TM} \iff f(w) \notin E_{TM} $. Therefore, using the same reduction function $f$, we have that $\overline{A_{TM}} \le_m \overline{E_{TM}} $. However, $\overline{E_{TM}}$ is Turing-recognizable and $\overline{A_{TM}}$ is not Turing-recognizable.

I understand the proof above I think. It seems I am misunderstanding something fundamental about mapping reductions, or that I am confused about some step in the reduction from $A_{TM}$ to $E_{TM}$ in the standard proof.

$\endgroup$
2
  • 1
    $\begingroup$ You should probably define $E_{TM}$ and $A_{TM}$ in order to make the question self-contained. $\endgroup$
    – Steven
    May 19, 2022 at 10:58
  • $\begingroup$ My choice would have been the straightforward proof by diagonalization that shows $E_{TM}$ is not computably enumerable had there been a poll for "the standard proof for the undecidability of $E_{TM}$" $\endgroup$
    – John L.
    May 20, 2022 at 1:47

2 Answers 2

4
$\begingroup$

Given $\langle M,w\rangle\in A_{TM}$, the mapping $f$ in the question maps $\langle M,w\rangle$ to $\langle M_1\rangle$, where Turing machine $M_1$ accepts input $x$ iff $x$ is $w$ and $M$ accepts $w$.

$f$ is NOT a mapping reduction from $A_{TM}$ to $E_{TM}$, since $M_1$ accepts $w$, i.e., $f(\langle M,w\rangle )=\langle M_1\rangle\not\in E_{TM}$ when $\langle M,w\rangle \in A_{TM}$.

On the other hand, $f$ is a mapping reduction from $A_{TM}$ to $\overline{E_{TM}}$, if we let $f$ map any string not of the form $\langle M,w\rangle$ to $\langle M_{\text{loop}}\rangle$, where $M_{\text{loop}}$ is a Turing machine that runs forever for all inputs.


The reason why $A_{TM}$ is not mapping reducible to $E_{TM}$ is given by the proof in the question.

$\endgroup$
1
$\begingroup$

Note: This answer was given before the definition of $A_{TM}$ was added to the question and was assuming the following definition instead $A_{TM} = \{ \langle T \rangle \mid L(T) = \Sigma^* \}$.

$E_{TM}$ is mapping reducible to $A_{TM}$. Here is a sketch of a possible reduction:

Given (the description of) a Turing Machine $T$, compute (the description of) a Turing Machine $T'$ that behaves as follows:

  • $T'$ takes two inputs, a word $w$ and a non-negative integer $n$.
  • $T'$ simulates $T$ with input $w$ for $n$ steps.
  • If the simulation of $T$ accepts within $n$ steps, $T'$ rejects.
  • Otherwise, $T'$ accepts.

If $T \in E_{TM}$ then for every word $w$ and every integer $n$, the simulation of $T(w)$ either rejects or does not halt within $n$ steps, causing $T'$ to accept. Therefore $T' \in A_{TM}$.

If $T \not\in E_{TM}$, then there is some word $w$ for which $T(w)$ accepts. Let $n$ be the number of steps taken by $T(w)$ to accept. The Turing Machine $T'$ with inputs $w$ and $n$ rejects. Therefore $T \not\in A_{TM}$.

$\endgroup$
2
  • $\begingroup$ Hi, I edited the question to make it clearer. $\endgroup$ May 19, 2022 at 12:15
  • $\begingroup$ This answer was given before you added the definition of $A_{TM}$ and is using the different definition $A_{TM} = \{ \langle T \rangle \mid L(T) = \Sigma^* \}$. $\endgroup$
    – Steven
    May 19, 2022 at 12:53

Your Answer

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

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