Question about a semi-decidable property of languages

Question

Consider the following property of recursively enumberable (RE) languages

$$ L = \{ J \in \text{RE} \mid J \cap L_{uni} \ne \emptyset \}$$

where $L_{uni}$ is the language of the Universal Turing machine.

I am wondering if $L$ is semi-decidable. That is (by definition) if the set $$ S = \{ \langle T \rangle \mid L(T) \in L\}$$ is recursively enumerable.

If I am not mistaken then this should be true because one can always construct a Turing machine $M$ that accepts a code $\langle T \rangle$ and (using non-determinism) generates the "right" input for $T$ and $T_{uni}$, verifies that both accept the generated word (simulating the machines) and if so accepts the supplied string.

Can someone verify this claim?

Answer 1

Let $M$ be any computably enumerable set and define the set $$J_M = \lbrace n \in \mathbb{N} \mid W_n \cap M \neq \emptyset\rbrace,$$ where $W_n$ is the $n$-th computably enumerable set. Then $J_M$ is a computably enumerable set because $$m \in J_m \iff W_n \cap M \neq \emptyset \iff \exists m . m \in W_n \land m \in M$$ is obviously a semidecidable condition, as c.e. sets are closed under finite intersections and existential quantification over $\mathbb{N}$.

We may now get your result by taking $M = L_{\mathrm{uni}}$.

If you are wondering about the "obviously semidecidable" condition, we can put in a bit more details: to semidecide whether $W_n \cap M \neq \emptyset$ just keep enumerating the elements of $W_n$ and $M$ in parallel, until an $m$ appears in both enumerations.