Showing this language is not decidable by rice theorem or reduction

373 Views Asked by At

Consider this language:

L = {<M1,M2> : M1 and M2 are TMs and L(M1) contained in L(M2) contained in {1}*}

Intuition says that it's undecidable, though can it be shown with rice's theorem? if not, maybe by reduction?

any help will be appriciated

Thanks

1

There are 1 best solutions below

1
On BEST ANSWER

Let $E$ be the set of TMs that accept nothing, and let $G$ be one fixed element of $E$. Then, if $M$ is any TM, we have that $M\in E$ if and only if $\langle M,G\rangle\in L$, where $L$ is defined as in the question. So, if $L$ were decidable, $E$ would also be decidable, contrary to Rice's theorem.