Write your proof in the format and style adopted in the

Question

Assignment

Type and appropriately format your proof. Handwritten answers will not be accepted. You may use any word processor to type and format your answer. Turn in a hard-copy of your proof.

Prove that the following language is undecidable.

PSUPER_TM = {(M₁, M₂) | TM M₁ accepts a proper superset of the strings that TM M₂ accepts}

As a decision problem, PSUPER_TM is the problem of determining whether L(M₁) ⊃? L(M₂) is true for any two given TMs M₁ and M₂.

Write your proof in the format and style adopted in the class, with notes/comments to clarify the steps of the proof and the TM's used or created in the proof. All TM's must be clearly specified and/or defined in the format adopted in the class.

Your proof may make use of the facts that the languages HALT_TM, A_TM, E_TM, ALL_TM, NOTEMPTY_TM, FINITE_TM, and EQ_TM are provably undecidable.