Self Doubt

Question

If for every RE there exist a TM that accepts it, is it possible that for 2 different RE languages there exists a single TM that accepts them?

Answer 1

This problem can be solved using the closure property of REL. The language generated by union of 2 RELs is a new REL. 

And as the new generated language is REL that means we can build a Turing Machine for it. This new TM will accept both the languages.

REL1 ∪ REL2 ≡ REL.

 

Comments

Then build a TM for sigma* and it'll accept any language 😉

---

You may have two different TMs  which accept same language. But you can't have one TM which accepts two different languages.

 

Language accepted by TM means, produces Yes for the strings which are in it. And No for other strings.