Exercise $9\mathrm{.}2\mathrm{.}1$: Show that the halting problem, the set of $($M$,$w$)$ pairs such that M halts $($with or without accepting$)$ when given input w is RE but not recursive. $($See the box on "The Halting Problem$$ in Section $9\mathrm{.}2\mathrm{.}4.)$ The Halting Problem One often hears of the halting problem for Turing machines as a problem similar to Lu $$ one that is RE but not recursive. In fact, the original Turing machine of A$.$ M$.$ Turing accepted by halting, not by final state. We could define HM for TM M to be the set of inputs w such that M halts given input w$,$ regardless of whether or not M accepts w$.$ Then, the halting problem is the set of pairs $($M$,$ w$)$ such that w is in H$($M$).$ This problem$/$language is another example of one that is RE but not recursive. Accept Accept W $-$ Copy Copy w $111$ w $-$ Hypothetical algorithm M for Reject Reject M$\text{'}$ for L$,$