0
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.