1
$\begingroup$

I know the reduction to from $A_{TM}$ to $HALT$. But is the following reduction from $HALT$ to $A_{TM}$ correct?

We are looking for total computable function $f$ mapping from $HALT$ to $A_{TM}$. The following TM $F$ calculates the reduction $f$.

F = on input <T, w>
    create the following TM T':
    T' = on input v:
       start T on v
       if T accepts or rejects, *accept*
    return <T',w>

I think the line if T accepts or rejects, *accept* is correct, but it would be great if someone could check this.

Edit: I found the following slides, but I don't think the construction in there is correct: http://slideplayer.com/slide/13791105/

$\endgroup$

2 Answers 2

2
$\begingroup$

There are multiple notions of "reduction." You've correctly described a many-one reduction of $HALT$ to $A_{TM}$. The reduction you've linked to (with the proof on slide 24 of the deck you linked) is instead a truth-table reduction. These are more general objects (so your result is stronger). Each is in turn subsumed by the much broader notion of Turing reduction.

While many-one reductions are generally the default notion in complexity theory, Turing reductions and the resulting degree structure are the default in computability theory. Note that if all I want to do is prove the undecidability of some set, a Turing reduction from some known-to-be-undecidable set is sufficient.


First, let's explicitly recall the definitions of the languages involved:

  • $A_{TM}=\{\langle M,w\rangle: M$ halts and accepts on input $w\}$.

  • $HALT=\{\langle M,w\rangle: M$ halts on input $w\}$.

Your proposed reduction of $HALT$ to $A_{TM}$ is correct: given $M$, we can computably build a new machine $\hat{M}$ which accepts precisely those strings on which $M$ halts. (Basically, just replace all the "reject" states in $M$ by "accept" states.)


Now let's look at the other reduction which you linked to (the aforementioned slide 24, reproduced below).

Example reduction

  • Deciding $HALT$ using a procedure that decides $A_{TM}$ (“reducing $HALT$ to $A_{TM}$”)
    • On input $\left<M, w\right>$
    • Check if $\left<M, w\right>\in A_{TM}$
      • if yes, the[n] $M$ halts on w; ACCEPT
      • if no, then $M$ either rejects w or it loops [o]n $w$
    • construct $M'$ by swapping $q_{accept}$/$q_{reject}$ in $M$
    • check if $\left<M', w\right>\in A_{TM}$
      • if yes, then $M'$ accepts $w$, so $M$ rejects $w$; ACCEPT
      • if no, then $M$ neither accepts nor rejects $w$; REJECT

Basically, rather than going to "all halting states accept" the linked argument considers separately:

  • the original machine, and

  • the "contrary" machine which accepts exactly when the original one rejects and vice-versa.

An affirmative answer for either case in $A_{TM}$ ensures an affirmative answer for the original machine in $HALT$.

Off the top of my head I see no reason to do this rather than follow your argument, especially because it yields a weaker result, but it is correct and is enough to prove the broader claim in the slides, namely that $A_{TM}$ is undecidable.

$\endgroup$
0
$\begingroup$

Your solution looks correct. I have a concern that since we have assumed a decider for ATM, so M will either accept any word 'w' or reject it; in either case our constructed decider for HaltTM would output yes. Precisely, there would be no case when it outputs no. But that does not violates the condition of decidability and is perfectly alright!

$\endgroup$
1
  • $\begingroup$ Your concern is unfounded. The reduction translates an instance $\langle T,w\rangle$ of $\mathit{HALT}_{\mathsf{TM}}$ to an instance $\langle T',w\rangle$ of $A_{\mathsf{TM}}$ such that $T$ halts on $w$ iff $T'$ accepts $w$. In other words, it works as intended. In case $T$ does not halt on input $w$, $T'$ will also fail to halt on input $w$. When run on $\langle T',w\rangle$, a (hypothetical) decider for $\mathit{A}_{\mathsf{TM}}$ will reject. $\endgroup$
    – Kai
    Commented May 13 at 5:38

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.