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

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?

• Rice's theorem seems irrelevant. Nov 29, 2022 at 21:49

#### 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$$

• How can I solve $L_U ≤_m \bar S$? I cant figure it out. I cant just check wheter $x$ is not $aww^R b$ Dec 1, 2022 at 19:33
• Please check my updated answer. The only difference in construction is replacing "accept" at one place with "loop forever". Dec 1, 2022 at 19:48