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 existed, construct a program that loops when predicts halting and stops when it predicts nonhalting. Running 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.
The Halting problem is a fundamental concept in computability theory, introduced by British mathematician and logician Alan Turing in 1936. It is a decision problem that can be stated as follows: Given a description of a program (or Turing machine) and an input, determine whether the program finishes running (halts) or continues to run indefinitely. Turing proved that there is no general algorithm that can solve the Halting problem for all possible program-input pairs.
The canonical undecidable problem.
New to topics? Read the docs here!