2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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