PROOF :We assume that Turing machine H decides ATM for the purpose of obtaining a contradiction. We construct the following machine B.

B =“On input w:

  1. Obtain, via the recursion theorem, own description ⟨B⟩.
  2. Run H on input ⟨B, w⟩.
  3. Do the opposite of what H says. That is, accept if H rejects and reject if H accepts.”

I can not understand point 3 I want to know its logic

Does this have same logic as the halting problem where if we get a yes it loops forever so it does not halt and if it does not halt we get a no then it halts?

  • $\begingroup$ Yes. Same idea, different expression. $\endgroup$ – Rick Decker Sep 6 '19 at 16:49

Your Answer

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

Browse other questions tagged or ask your own question.