= Halting problem
{wiki}
The <halting problem> asks, given a program and an input, whether running that program on that input eventually stops. It is undecidable: no total <algorithm> answers correctly for every encoded program and input.
If a decider $H(P,x)$ existed, construct a program $D(P)$ that loops when $H(P,P)$ predicts halting and stops when it predicts nonhalting. Running $D$ on its own description contradicts either prediction. Halting instances are nevertheless <computably enumerable>, since finite simulations eventually witness any halt. If nonhalting instances were also <computably enumerable>, <dovetailing> the two recognizers would decide the problem, so their complement is not enumerable.
Back to article page