Question about reduction Proof

I've recently seen a proof that the set of Turing machines $$L = \{encode(M) |L(M) \text{is closed under reversal}\}$$ is not decidable.

The proof used following idea: Reduce from the $$A_{TM}$$ problem by taking input $$\langle M, w \rangle$$ and by constructing $$M'$$ such that $$L(M') = \text{some language that is closed under reversal; if M accepts w}\\ L(M') = \text{some language that isn't closed under reversal}; \text{if M rejects w}$$

Now, I have some confusion about this proof. I can see the contradiction because an algorithm for $$L$$ would solve $$A_{TM}$$. However, how can you construct $$M'$$ in such a way? Wouldn't that require to already have solved $$A_{TM}$$ to begin with? How would you notice that w is rejected or accepted without using $$A_{TM}$$ and how would you build the Turing machine $$M'$$ based on that observation in more detail? I am quite confused about that. It seems contradictory to me, in a way. I hope someone can help me with that!

1 Answer

You are right. Its certainly hard (or not intuitive) to why its possible to do such a reduction, since it intuitively says that we know how to solve $$A_{TM}$$. The key point lies in constructing $$M'$$ in such a way that we won't need to know beforehand if $$M$$ accepts or rejects $$w$$.

Since this question has been asked before, take a look at my answer for it