Please help me get this right,
The question asks Is L Turing decidable ?
where L ={<M> : M is a TM, which accepts some palindrome
My thoughts on the poof to show that it is undecidable are the following. Assume L is decidable and let R be a decider for that language. I will construct a decider S for A_tm using R as a subroutine.
S = on input <M,w>
1. constructs TM M_w = on input x if x != (some palindrome ex 1^n 0 1^n) reject else run M on w if M accepts => accept; if M rejects => reject.
2. Run R on M_w
3. If R accepts => accept, if R rejects => reject.Note: Assume M accepts w then L(M_w) = some palindrome, Then R(M_w) accepts it => S accepts. Assume M rejects or loops then L(M_w) = empty set. Then R(M_w) rejects => S rejects.
Now since we know that A_tm is undecidable , assumption was wrong => L is undecidable.
$\endgroup$ 21 Answer
$\begingroup$Yes, this reduction looks correct. If $M$ rejects $w$, then the language of $M_w$ is empty. If $M$ accepts $w$, then the language of $M_w$ is $\{\mathtt{abcdcba}\}$ (or whatever the hardcoded palindrome is.)
Hence $M_w$ accepts a palindrome if and only if $M$ accepts $w$. We have reduced the TM acceptance problem to the problem of deciding whether a Turing machine's language contains a palindrome. Given $M$ and $w$, we create the machine $M_w$ and run the palindrome decider on it. The palindrome decider returns true if $M$ accepts $w$ , and false if it doesn't. But the TM acceptance problem is undecideable; hence so is the palindrome problem.
$\endgroup$
