How to reduce universal language to language of all turing machines that deduce all palindromes?

Question

Let $S$ be language $$\{\langle M\rangle \mid(\forall x \in \Sigma^*)[x \in L(M) \iff x^R \in L(M)]\}.$$

How can I show that $L_U \le_m S$ and $L_U \le_m \bar S$ where $L_U$ is universal language and $\le_m$ means it is m-reducible (or simply reducible)? Can it be done via Rice's theorem?

Answer 1

Show $L_U \le_m S$

Let $v=\langle T, w\rangle$, where $T$ is a Turing machine and $w$ is an input string to $T$. Fix two different input symbols $a$ and $b$. Construct Turing machine $M_v$ that upon input $x$, check whether $x$ is $aww^Rb$.

• If it is, accept.
• Otherwise, check whether $x$ is $bww^Ra$.
  • If it is, simulate $T$ upon input $w$.
  • Otherwise, accept.

It is straightforward to check that $v\in L_U$ $\iff$ $\langle M_v\rangle\in S$. The construction from $v$ to $M_v$ is computable. Hence $L_U \le_m S$

Show $L_U \le_m \bar S$

Let $v=\langle T, w\rangle$, where $T$ is a Turing machine and $w$ is an input string to $T$. Fix two different input symbols $a$ and $b$. Construct Turing machine $M_v$ that upon input $x$, check whether $x$ is $aww^Rb$.

• If it is, loop forever.
• Otherwise, check whether $x$ is $bww^Ra$.
  • If it is, simulate $T$ upon input $w$.
  • Otherwise, accept.

It is straightforward to check that $v\in L_U$ $\iff$ $\langle M_v\rangle\in \bar S$. The construction from $v$ to $M_v$ is computable. Hence $L_U \le_m \bar S$