1
$\begingroup$

A widely used example of reductions, is a reduction of $A_{TM}$ to $HALT_{TM}$.

How to show the opposite reduction, meaning of $HALT_{TM}$ to $A_{TM}$, if possible.

$\endgroup$
1
$\begingroup$

A many-one reduction from $HALT_{TM}$ to $A_{TM}$ means that all instances of the $HALT_{TM}$ problem are transformed to an instance of $A_{TM}$ (can be just one instance), such that if $A_{TM}$ is turing-recognizable then $HALT_{TM}$ is also turing-recognizable.

This reduction can be done by encoding a $TM$ $N$, such that $N$ accepts input string $\langle M,w\rangle$ iff $M$ halts with input string $w$. So if $M$ halts with input $w$, it means that $\langle M,w\rangle \in HALT$, which implies that $N$ accepts $\langle M,w\rangle$, and that the instance $\langle N,\langle M,w\rangle\rangle\in A_{TM}$.

$\endgroup$
  • $\begingroup$ That's quite an obscure explanation. Could you make it more plattable? $\endgroup$ – Ran G. Feb 8 '18 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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