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$
  • 4
    $\begingroup$ Rice's theorem comes to mind... it's proof is rather easy to adapt for such cases. $\endgroup$ – vonbrand Jan 27 '16 at 2:16
  • $\begingroup$ Do you mean to say we can solve this using rice theorem also? Is yes, how? $\endgroup$ – anir Nov 26 at 9:58
1
$\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$
  • $\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$ – user1745470 Jan 26 '16 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$ – Denis Pankratov Jan 26 '16 at 22:26
  • $\begingroup$ @user1745470 And you yourself proposed another route. $\endgroup$ – Raphael Jan 28 '16 at 11:01

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.