How would one reduce HaltTM to ATM
For the sake of argument we will assume ATM is decidable. Now we are going to show a way to decide HaltTM using ATM decider, and thus reach a contradiction, since we know HaltTM is undecidable.
Details:
Since ATM is decidable then ATM(Complement) is also decidable, We take TM R that decides ATM and another S that decides ATM(Complement), we use those to build X,
given input &lt; M, w > a turing machine description and it's input w, Run R on given input if accepts accept, if rejects then run S on input, if accepts accept, if rejects reject. This way we have insured that X will reject only machines that do not halt,and accepts all others. So we have used ATM decider to decide HALT but HaltTM is undecidable so we conclude that ATM wasn't from the start decidable.