Proving Rice's theorem extension

Question

Let a non-trivial $C \subseteq RE$

Prove $\Sigma ^* \notin C \implies L_c \notin RE$

$L_c$ satsifies $L_c=\{\langle M \rangle|L(M) \in C \}$

---

First of all, I searched this site for over an hour looking for an already written answer so I am sorry if this is a repeat.

I've been trying for a long time to make this work but something is stuck. My main idea was finding a reduction mapping from some non recursively enumerable language which will allow me to deduce that $L_c$ isn't recursively enumerable.

Since $C$ is non-trivial I have some language $A \in C$ with a turing machine $M_A$ s.t $L(M_A)=A$ (since $A \subseteq RE$).

Now i can define a mapping function $f$ from $HALT^c$ to $L_c$ s.t given $<M,x>$ we return $<M_x^A>$.

$M_x^A$ on some input $w$ behaves:

1. Run $M$ on $x$
2. Simultaneously run $M_A$ on $w$
3. If $M$ stops then accept
4. Else, accept $\iff$ $M_L$ accepts

This would work except in the case where $<M,x> \in HALT^c$ since my machine would never stop running and will never accept $w$ even though I wish it to.

How can i fix this?

Answer 1

You need to run the machines $M$ and $M_A$ in parallel, as we cannot simply run the machines consecutively -- this is a basic trick, where we cannot simply wait for one machine to halt as it may not, and this way we miss the opportunity to run the other machine. As we don't know in advance which machine halts, or if some machine halts, we run them in parallel to make sure we find out when some of the machine halts regardless of the behaviour of the other machine. Basically, we work in iterations $i = 0, 1, 2, \ldots$, where in iteration $i$, we simulate each machine for $i$ steps. I leave the details to you.

So this is what you need to do: let $A \in C$, and $M_A$ be a machine with $L(M_A) = A$. Then, a reduction from $\overline{A_{TM}} = \{ \langle M, w\rangle: \text{$M$ does not accept $w$}\}$ to $L_C$ is defined as follows. Given input $\langle M, w\rangle$ for the reduction, the reduction outputs $\langle T\rangle$, where $T$ is a TM that operates as follows. On input $x$ for $T$, $T$ simulates the run $M_A$ on $x$, and the run $M$ on $w$ in parallel and accepts if at least one of simulated runs is accepting. Regarding correctness, if $M$ does not accept $w$, then the run of $M$ on $w$ never reaches an accepting state, and so the behaviour of $T$ on $x$ is identical to that of $M_A$ on $x$, and thus $L(T) = L(M_A) \in C$. Conversely, if $M$ accepts $w$, then $T$ accepts all its inputs, and thus $L(T) = \Sigma^* \notin C$.

Note that I defined the reduction from $\overline{A_{TM}}$ to add some simplicity, but you can define a reduction from $\overline{HALT}$ similarly.