Halting problem
In computer science, the halting problem is a concept first put forth by Alan Turing in 1936. It asks whether we can create a program with a given input that can tell us if another program will eventually stop running (halt) or keep running forever in an endless loop. The halting problem is an example of an undecidable problem, which means there isn't a solution for all possible inputs.
Proving the halting problem
Turing's proof of the undecidability of the halting problem is based on a technique called diagonalization. He started with the assumption there is a program that could solve the halting problem for all possible inputs. Then, he constructed another program that would produce an outcome that counters what the first predicts, thus rendering that original prediction incorrect. Essentially, if you had an algorithm program that could correctly determine if any program halts or not, you could create another one that contradicts its output.
This paradoxical situation shows no general algorithm can solve the halting problem. The undecidability of the halting problem implies that there are limits to what computers, even in principle, can calculate or decide.