# Is L Turing decidable?

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.

• When you say "$x !=$ (some palindrome)", the palindrome has been fixed right ? – Max Aug 10 '17 at 5:24
• Yes. Some palindrome is fixed, one can choose his favorite one. – acagu Aug 11 '17 at 18:48

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.