1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Rice's theorem seems irrelevant. $\endgroup$
    – John L.
    Nov 29, 2022 at 21:49

1 Answer 1

1
$\begingroup$

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$

$\endgroup$
2
  • $\begingroup$ 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$ $\endgroup$
    – Rikib1999
    Dec 1, 2022 at 19:33
  • 1
    $\begingroup$ Please check my updated answer. The only difference in construction is replacing "accept" at one place with "loop forever". $\endgroup$
    – John L.
    Dec 1, 2022 at 19:48

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.