Mapping reduction - Bit Flip

Question

Let $L=\{<M> | M$ is a TM, $L(M)\ne \emptyset$ and $\forall x\in L(M), \overline{x} \notin L(M) \}$

While $\overline{x}$ is the bit flip of $x$.

I want to show a mapping reduction to prove that this language is either in R / RE / coRE or none of them.

My intuition is that this language does not belong to any of the classes, so I am trying to show to reductions:

$\overline{E_{TM}} \le_m L$ and $E_{TM} \le_m L$.

Am I in the right direction?

Because I can't find any mapping function to help me with that.

Thanks a lot!

Answer 1

These are just ideas, not actual redcutions.

The language indeed seems to be neither RE, nor coRE. It might help to identify what part of the language makes it not RE or not coRE:

• the $L(M)\neq \emptyset$ is a RE part: it can be verified by dovetailing. However, the $\forall x\in L(M), \overline{x}\notin L(M)$ property cannot be verified: not only you'd need to browse all possible $x$, the property $\overline{x}\notin L(M)$ cannot be verified. What I suggest is trying to make a reduction from $L_{\forall} = \{\langle M\rangle \mid L(M) = \Sigma^*\}$, a well-known non-RE language, to your language. To not be bothered by the first part, you just have to guarantee that your reduction create a MT with a non empty language.
• the $\forall x\in L(M), \overline{x}\notin L(M)$ part is coRE: you "just" need to find a $x$ such that $x\in L(M)$ and $\overline{x}\in L(M)$ as a counter-example. This can be done by dovetailing. However, the $L(M)=\emptyset$ is not a coRE part: you'd need to verify for all $x$ that $x\notin L(M)$. This cannot be done. I suggest here that you make a reduction from $L_{\emptyset} = \{\langle M\rangle\mid L(M) = \emptyset\}$, a non-RE language, to the complement of your language. To not be bothered by the second property, just insure that for all $x\in\Sigma^*$, $x\in L(M) \iff \overline{x}\notin L(M)$.

Hope that helps.