Show this language is undecidable: SubsetTM = {< M1,M2 > | M1 and M2 are TMs and L(M1) L(M2)}.?

Question

I have no idea where to begin with something like this other than i know that you must use a contradicton to prove it and u can use the reduction technique. However my professor wasnt very clear on how it all went together, any help please?

EQTM = {< M1,M2 > | M1 and M2 are TMs and L(M1) = L(M2)}.

this part is given as undecidable

sorry that should say L(M1) is a subset of L(M2) yahoo doesnt like the subset symbol i guess

Answer 1

If you fix the question, I'll be able to answer :) (and L(M1) *what* L(M2)?)

Ah, there we go.
The basic idea is to assume the language is decidable, and then try to use that to prove that EQTM is decidable - that will give you a contradiction, thus the original language is undecidable.

So, assume that SubsetTM is decidable, and lets say we are given as input to EQTM.
Firstly, give as input to SubsetTM. If it tells us that L(M1) is not a subset of L(M2), then we return false, as they can't be equal.
Then give as input to SubsetTM. If it tells us that L(M2) is not a subset of L(M1), then we return false, as they can't be equal.
Otherwise we return true; since each language is a subset of each other, they must be equal.

Thus, if SubsetTM is decidable, so is EQTM; therefore SubsetTM is undecidable.