Reference no: EM131453140

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.