1. This problem explains an elementary proof that LHALT is undecidable. This was the first "existence" proof for an undecidable language, and it dates back to Alan Turing. (a) Suppose there exists a Turing Machine M that decides LHALT. Using M, design a Turing Machine M' such that for any Turing Machine T, M'((T)) halts if and only if M T), (T)) rejects. Hint: A Turing Machine can deliberately loop indefinitely. (b) Design an input z for M' that creates paradoxical behavior, and conclude that LHALT is undecidable