The language of machines that accepts all palindromes is not Turing recognizable

Question

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$)?

Answer 1

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.

Answer 2

Let $M_p$ be a TM that decides palindromes with runtime on $x$ at least $|x|$. Given $\langle M \rangle$ construct $\langle M' \rangle$ where $M'$ on $x$ behaves as follows:

• Run $M$ on $\langle M \rangle$ and $M_p$ on $x$ in "parallel" (i.e. step by step, on separate cells, e.g. $M$ only uses odd cells, and $M_p$ uses only even cells of the tape).
• If $M$ on $\langle M \rangle$ terminates, $M'$ rejects unconditionally.
• If $M_p$ on $x$ terminates and $M$ on $\langle M \rangle$ is still continuing the computation at this step, $M'$ terminates the simulation of $M$ and outputs according to $M_p$ on $x$.

Note that $M$ on $\langle M \rangle$ does not halt if and only if $M'$ decides the language of palindromes. (Why?)