[Math] Is L Turing decidable

turing-machines

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.

Best Answer

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.

Related Question