the halting problem
Suppose you wrote a tool that reads any program plus its input and tells you, without ever running it, whether that program will eventually finish or instead get stuck in an infinite loop. Such a tool would be a dream: no more frozen apps, no more hanging servers. The halting problem asks whether such a tool can exist. Phrased as a yes/no question: given the description of a machine M and an input w, does M halt (finish) on w? The shocking answer, proved by Alan Turing in 1936, is that no algorithm can answer this question correctly for every possible (M, w). The problem is undecidable.
Let us be careful about what this does and does not say. It is easy to decide halting for SOME programs: a program with no loop always halts, and a program whose only line is while(true) {} obviously never halts. The claim is about a SINGLE general algorithm that must work for ALL machine-input pairs. We can package every such pair as a string, giving the language HALT = { the encoding of (M, w) : machine M halts on input w }. Asking the halting problem is asking whether HALT is decidable, that is, whether some Turing machine always stops and answers correctly whether a given (M, w) is in HALT. Turing proved no such decider exists.
This is not a statement about being slow or hard. The halting problem is not merely expensive to solve; it is provably impossible to solve in general, no matter how much time, memory, or cleverness you are given. A would-be halt checker can sometimes refuse to answer (saying 'I do not know'), or it can answer fast on easy cases, but it can never be a total, always-correct decider. This single result is the gateway to all of computability theory: once you accept that one precise question has no algorithm, a whole family of natural questions about programs falls with it.
Define collatz(n): while n != 1, if n is even set n = n/2 else set n = 3n+1. Does collatz halt on every starting n? Nobody knows. A general halt checker would settle this and countless other open problems at a keystroke, which is one informal reason to suspect no such checker can exist.
The halting problem packaged as a language: HALT = { (M, w) : M halts on w }, which is undecidable.
Undecidable does not mean 'undecidable for every input'. Many specific programs are easy to analyze; what is impossible is one algorithm that is correct on all (M, w) pairs at once.