I'm studying reducidability in Sipser Book and watching his videos, but I couldn't fully understand his proof of $A_{TM}$ reducidability to $𝐸_{𝑇𝑀}$ (p. 218, 3rd ed).
Consider this extract:

M1 = “On input x:

  1. If x $\neq$ w, reject .
  2. If x $=$ w, run M on input w and accept if M does.”

Where comes the input "x"? is the same input "w"? who will inform "x" to the M1 machine? will be S machine? If is S, will be the w?

If one could construct this machine, could this solve the $A_{TM}$ as well? Thus, would be this machine undecidable in first place? Would this fact invalidate the proof of $𝐸_{𝑇𝑀}$ undecidability?

  • $\begingroup$ (reducidability you're losing me.) Effective line breaks in markdown: append two blanks to preceding line. $\endgroup$
    – greybeard
    Commented May 7 at 19:51


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.