Theory of Computation - Decidability

Question

Is this language Decidable ?

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

Where Ɛ = Epsilon

EDIT => 

I think it is the non-trivial property of TM making it undecidable.

By applying rice theorem 1,

Take T_yes = Σ^*  and T_no = (0) , making it REL.

Comments

property of TM or property of language of TM? Rice's theorem is applicable only for second.

Though answer would be same how you got $T_{yes}$ and $T_{no}$ is not clear as each of them is made from two other TMs as per the definition given in question.

---

Sir, this is a property of language, right ?

If not, then how to do it by reducibilty .

I am not getting how to do reduction from halting problem .

Answer 1

Rice’s Theorem

We will show that every non-trivial property of languages of Turing machines is undecidable (Rice’s theorem). To show this theorem, we will formalize what properties of languages are and what it means for them to be non-trivial for Turing machines.

Let 2{0,1}∗2{0,1}∗ be the set of all languages over the binary alphabet. A propertyof languages is a subset P⊆2{0,1}∗P⊆2{0,1}∗. We say LL satisfies PP if L∈PL∈P and we say that LL violates PP if L∉PL∉P. For example, we can choose PP to be the set of languages that contain the string 00000000.

We say that PP is a non-trivial property of languages of Turing machines if there exists Turing machines MYMY and MNMN such that L(MY)L(MY) satisfies the property and L(MN)L(MN) violates the property. Here is an example of a property that is non-trivial for languages of Turing machines,

Pempty={∅}.Pempty={∅}.

The property is non-trivial because there are Turing machines that recognize the empty language and there are Turing machines that recognize a non-empty language. Here is an examples of a property that is trivial for languages of Turing machines,

Answer 2

It is undecidable poblem .Any problem which is associated with turing machine always undecidable.