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

ignougroup
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,wrangle$ 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)inoverline{A_{TM}}$, then $M$ will never accept $w$ and so $N$ will accept all palindromes, so $langle:N:ranglein L$.
  • If $(langle:M:rangle,w)notinoverline{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:ranglenotin L$.

Finally, we conclude that $(langle:M:rangle,w)inoverline{A_{TM}}$ if and only if $langle:N:ranglein 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