# Mapping reduction - Bit Flip

Let $$L=\{ | 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!

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.

• Indeed, thank you! Just have a quick question, why do you say that $L(M)\ne\emptyset$ is a RE part, and $L(M)=\emptyset$ is a coRE part? I think it should be the opposite, because $E_{TM}=\{<M>|M~is~a~TM~\wedge~L(M)=\emptyset\} \in coRE$ and $\overline{E_{TM}}=\{<M>|M~is~a~TM~\wedge~L(M)\ne\emptyset\} \in RE$
– Geo
Nov 26, 2022 at 9:19
• Not sure about your comment: the languages you describe just confirm my point. Nov 26, 2022 at 9:22
• What do you mean by "is a RE part" for example? Thanks! :)
– Geo
Nov 26, 2022 at 10:12
• What I mean by $P(M)$ for a property $P$ is that $\{\langle M \rangle \mid P(M) \text{ is verified}\}$ is a RE language. For example, "$L(M)\neq \emptyset$ is a RE part" means that $\{\langle M \rangle \mid L(M) \neq \emptyset\}$ is RE. Nov 26, 2022 at 10:17
• Got it! Thanks!
– Geo
Nov 26, 2022 at 15:57