1
$\begingroup$

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!

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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$ $\endgroup$
    – Geo
    Nov 26, 2022 at 9:19
  • $\begingroup$ Not sure about your comment: the languages you describe just confirm my point. $\endgroup$
    – Nathaniel
    Nov 26, 2022 at 9:22
  • $\begingroup$ What do you mean by "is a RE part" for example? Thanks! :) $\endgroup$
    – Geo
    Nov 26, 2022 at 10:12
  • $\begingroup$ 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. $\endgroup$
    – Nathaniel
    Nov 26, 2022 at 10:17
  • $\begingroup$ Got it! Thanks! $\endgroup$
    – Geo
    Nov 26, 2022 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.