Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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