[Solved]: The language of machines that accepts all palindromes is not Turing recognizable

Problem Detail: 

I have this question:

$L = \{\langle M \rangle | M$ is TM that accepts every palindrome over its alphabet $\}$

Proof that $L$ is not Turing-recognizable by showing reduction from other non Turing-recognizable language.

What I have tried to do is to show reduction from $A_{TM}$ (Accept problem) to $\bar L$, and I didn't succeed to show one. I tried to create a new machine that will reject some palindrome(s) if $M$ accepted $w$ when $\langle M,w\rangle$ is the input of $A_{TM}$. But if $M$ will not halt on $w$, then the palindrome(s) will reject also by mistake.

So how can I show reduction from $A_{TM}$ to $\bar L$ (or $\bar {A_{TM}}$ to $L$)?

Asked By : user1745470

Answered By : Rick Decker

Here's a reduction $\overline{A_{TM}}\le L$. Define the mapping from $(\langle\:M\:\rangle,w)\rightarrow \langle\:N\:\rangle$ where

N(x) =    if x is a palindrome       run M on w for |x| moves       if M hasn't accepted yet          accept 

Now,

• If $(\langle\:M\:\rangle,w)\in\overline{A_{TM}}$, then $M$ will never accept $w$ and so $N$ will accept all palindromes, so $\langle\:N\:\rangle\in L$.
• If $(\langle\:M\:\rangle,w)\notin\overline{A_{TM}}$, then $M$ will accept $w$ in some number, $m$ of moves, so $N$ will accept all and only those palindromes of length $<m$, so $\langle\:N\:\rangle\notin L$.

Finally, we conclude that $(\langle\:M\:\rangle,w)\in\overline{A_{TM}}$ if and only if $\langle\:N\:\rangle\in L$ and since $\overline{A_{TM}}$ is unrecognizable, then so must $L$ be.

To be fair, this is almost exactly Denis' argument, just specified for the reduction you required. It's a useful idiom that can be used to show that many languages are unrecognizable.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52329