Question

Let M₁ and M₂ be arbitrary Turing machines. Prove that the problem “L(M₁ ) ⊆ (M₂ ) ” is undecidable.

Answer 1

`Hey,

Note: Brother in case of any queries, just comment in box I would be very happy to assist all your queries

We will show that ATM ≤m L₁.

L₁ = {M₁, M2 ) | L(M₁) ⊆ L(M₂)}.

To Proove : L₁ is undecidable

Description of the reduction

Input: (M, w)

i. Construct a machine N₁ as follows:

N1 ignores its input x, simulates M on w and ACCEPTS if and only if M accepts w (Observe

That L(N₁) = Σ∗ if M accepts w and is ∅ otherwise).

ii. Construct another TM N₂ that always accepts its input (i.e., L(N₂) = Σ∗).

Output: (N₂, N₁)

Proof of correctness

If M accepts w, then L(N₁) = Σ∗ and thus L(N₂) ⊆ L(N₁).

On the other hand, if M does not accept w, then L(N₁) = ∅, thus L(N₂) is not a subset of L(N₁).

Therefore,

M accepts w ⇐⇒ L(N₂) ⊆ L(N₁).

Since we know that ATM is undecidable, therefore L₁ is undecidable.

Kindly revert for any queries

Thanks.