The Halting Problem

We define formally the Halting Problem, ${\text{HALT}}_{TM}$, with:

• An input of an encoding of a Machine $code(M)$ and an input word $w\in {\Sigma }^{\ast }$.
• An output of true iff $M$ terminates on input $w$.

$${\text{HALT}}_{TM}=\{⟨code(M),w⟩:M\text{ terminates on input }w\}$$