2
$\begingroup$

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

$\endgroup$
2
  • 4
    $\begingroup$ Rice's theorem comes to mind... it's proof is rather easy to adapt for such cases. $\endgroup$
    – vonbrand
    Jan 27, 2016 at 2:16
  • $\begingroup$ Do you mean to say we can solve this using rice theorem also? Is yes, how? $\endgroup$
    – RajS
    Nov 26, 2019 at 9:58

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ But as I said, the question was: Proof that $L$ is not Turing-recognizable by showing reduction from other non Turing-recognizable language. $\endgroup$ Jan 26, 2016 at 22:24
  • $\begingroup$ Yes, what I wrote is a reduction of this sort. $L' = \{ \langle M \rangle \mid M \text{ does not halt on } \langle M \rangle \}$ is not Turing-recognizable. $\endgroup$ Jan 26, 2016 at 22:26
  • $\begingroup$ @user1745470 And you yourself proposed another route. $\endgroup$
    – Raphael
    Jan 28, 2016 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.