Assuming that ATM is decidable, how to build a TM S that uses a TM R that takes as input and decides if M accepts w, to decide HaltTM, which we already know is undecidable, hence ATM isn't decidable. So how exactly do we go about this?


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 < 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.

  • $\begingroup$ The answer is incomplete. $\endgroup$ – Reeshabh Ranjan Apr 17 at 17:21
  • $\begingroup$ The answer is complete, but for some reason it's concealed. If I try to edit the answer I see it all, but when I save it then all words after ", given input" disappear. $\endgroup$ – Anwar Saiah Apr 18 at 15:58
  • $\begingroup$ Ok, I fixed it. there was "input<M,w)" which some how confused the editor or something, some spaces and changing ")" to ">" seem to have solved the issue. Thank you Reeshabh for bringing it to my attention. $\endgroup$ – Anwar Saiah Apr 18 at 16:02
  • $\begingroup$ The angle brackets probably would have been parsed as HTML tags, which can cause all kinds of weirdness. $\endgroup$ – David Richerby Apr 18 at 16:16

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.