Halting Problem

Definition

The halting problem $A_{TM}$ is the problem of determining, given a Turing Machine $M$ and input $w$, whether $M$ halts on $w$. $A_{TM}=\{⟨M,w⟩\mid M\text{ is a TM and }M\text{ halts on }w\}$

Undecidability

$A_{TM}$ is Recursively Enumerable Language but not Decidable. This proves strictly that $\text{Decidable}⊊\text{RE}$.