效绵鼎 The Halting Problem Theorem:HALT is not decidable (undecidable). Proof: o Suppose TM H decides HALT if M halts on x,H accept if M does not halt on x,H reject o Define new TM H':on input <M> if H accepts <M,<M>>,then loop if H rejects <M,<M>>,then halt consider H'on input <H'>: if it halts,then H rejects <H',<H'>>,which implies it cannot halt if it loops,then H accepts <H',<H'>>,which implies it must halt contradiction.Thus neither H nor H'can existThe Halting Problem Theorem: HALT is not decidable (undecidable). Proof:  Suppose TM H decides HALT ◼ if M halts on x, H accept ◼ if M does not halt on x, H reject  Define new TM H’: on input <M> ◼ if H accepts <M, <M>>, then loop ◼ if H rejects <M, <M>>, then halt  consider H’ on input <H’>: ◼ if it halts, then H rejects <H’, <H’>>, which implies it cannot halt ◼ if it loops, then H accepts <H’, <H’>>, which implies it must halt  contradiction. Thus neither H nor H’ can exist