L = { < M1,M2 > | M1,M2 are TM's and Ɛ ∈ L(M1) ∪ L(M2) }

Where Ɛ = Epsilon

I know that this language is undecidable, but why it is semidecidable too.

What i have tried is =>

Using Rice's Theorem, part 2

T(no) = (0,1)^+ and T(yes) = (0,1)*

Which gives that T(yes) is not a subset of T(no), and this says that it is semidecidable.

Is my understanding right ?

  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Raphael Sep 21 '16 at 14:31

Rice's second theorem can be used to show for some sets that they are not semi-decidable, but not the opposite.

In order to show that this set is semi-deciable, just follow the definition and construct a semi-decider.

Idea: Simulate both $M_1$ and $M_2$ on $\varepsilon$ simultaneaously using dovetailing. If either one halts and accepts, stop simulating and accept.


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.