the arithmetical hierarchy
Undecidability is not a single floor; it is a tower with infinitely many levels, each strictly harder than the one below. The arithmetical hierarchy is a map of that tower. It classifies decision problems by how many alternating 'for all' and 'there exists' quantifiers you need to describe them, and the more alternations a problem genuinely requires, the higher and harder it sits. At orientation level, the message is simple: there is rich structure above the decidable, and the halting problem is only the first step up.
The bottom of the tower is the decidable problems, those with an actual yes/no algorithm. The first level up splits in two. The recognizable (recursively enumerable, often labeled Sigma_1) problems are those expressible as 'there exists a witness such that a decidable check passes', for example 'M halts on w' means 'there exists a number of steps after which M has halted'. Their mirror image, the co-recognizable (Pi_1) problems, use 'for all', like 'M loops on every input'. Climbing higher, Sigma_2 allows 'there exists ... for all ...', Pi_2 allows 'for all ... there exists ...', and so on; each added alternation reaches a genuinely new, strictly larger class. The totality problem (does M halt on all inputs?) sits at Pi_2, provably harder than the halting problem itself. A problem that is r.e.-complete, like the halting problem, is the hardest problem at level Sigma_1, a target every other r.e. problem reduces to.
The hierarchy is built on relative computability: each level corresponds to what you could decide given an oracle for the level below. With a halting-problem oracle you can decide more, but a new, higher halting problem then becomes undecidable relative to that oracle, and so the tower rises forever (this is the jump operation). Two honest cautions. First, this is an orientation sketch; the precise theory (the Tarski-Kuratowski algorithm, completeness at each level, the strictness of the hierarchy) is a graduate topic. Second, do not confuse this hierarchy of UNDECIDABILITY with the complexity hierarchies (P, NP, PSPACE): those measure resources among decidable problems, while the arithmetical hierarchy lives entirely above the decidable line, measuring degrees of unsolvability.
Halting 'M halts on w' is 'there EXISTS a step count t by which M has stopped' (one existential, Sigma_1, recognizable). Totality 'M halts on EVERY input' is 'for ALL inputs x, there EXISTS a t by which M stops on x' (a for-all followed by a there-exists, Pi_2), which is provably higher up the tower than halting.
Counting alternating for-all / there-exists quantifiers ranks problems into ever-harder levels above the decidable.
This is a hierarchy of degrees of UNDECIDABILITY, not of running time. Do not confuse it with P/NP/PSPACE, which classify decidable problems by resources; the arithmetical hierarchy lives entirely above the decidable boundary.