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.

  • $\begingroup$ When you say "$x !=$ (some palindrome)", the palindrome has been fixed right ? $\endgroup$ – Max Aug 10 '17 at 5:24
  • $\begingroup$ Yes. Some palindrome is fixed, one can choose his favorite one. $\endgroup$ – 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.


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.