unrestricted grammar and Turing machines

633 Views Asked by At

Let $G$ be an unrestricted grammar. Then the problem of determining whether or not $L(G) = ∅$ is undecidable. Let $M_1$ and $M_2$ be two arbitrary Turing machines. Show that the problem $L(M_1) ⊆ L(M_2)$

This is a potential question for the exam and I have no clue how to solve it. Any help would be really appreciated.

1

There are 1 best solutions below

9
On

HINT: Use $M_1$ and $M_2$ to construct a Turing machine $M$ such that $L(M)=L(M_1)\setminus L(M_2)$. Construct a grammar $G$ such that $L(G)=L(M)$. Then ... ?