let $L = \{\langle M \rangle \mid M \text { is a TM, } \forall x \in L(M), x^R \notin L(M)\}$. Prove/disprove $L\in RE \backslash R$

Question

let $L = \{\langle M \rangle \mid M \text { is a TM, } \forall x \in L(M), x^R \notin L(M)\}$

($x^R$ is the reverse of $x$)

I need to determine and prove whether $L\in R , L\in RE \backslash R, \overline{L}\in RE\backslash R $ or none of them.

I'm pretty sure $L\in RE \backslash R$ because I think I know how to prove it's undecidable, but I'm having a hard time proving it's recognizable.

Any help would be appreciated.

Answer 1

Since you've mentioned that you know how to prove $\overline{L}$ is recognizable, I will only prove $L$ is not recognizable.

Recall that $L$ is decidable if and only if both $L$ and $\overline{L}$ are recognizable. Therefore, it suffices to show $L$ is undecidable.

Suppose for contradiction that $L$ is decidable, then there exists a decider $D$ for $L$. With $D$, the following algorithm can decide if a given TM $M$ accepts $\varepsilon$:

Given TM encoding $\langle M \rangle$

Let $M'$ be the following TM:
    Given input string $s$
    If $s = \varepsilon$:
        Simulate $M$ with $\varepsilon$
    else:
        Reject

Simulate $D$ with $\langle M' \rangle$
If $D$ rejects then accept else reject

This contradicts the fact that whether a given TM $M$ accepts $\varepsilon$ is undecidable. Therefore, $L$ is undecidable and hence $\overline{L} \in RE \setminus R$

The above algorithm works because $D$ accepts $\langle M \rangle$ if $``\forall s \in \Sigma^* \ M \text{ accepts } s \implies M \text{ does not accept } s^R"$, and rejects $\langle M \rangle$ if $``\exists s \in \Sigma^* \text{ such that } M \text{ accepts both } s \text{ and } s^R"$.