Can a computer decide?

In 1936 Alan Turing proved that no such checker can exist. The argument is short.

Suppose a program $H$ could take any program $P$ and input $x$ and always answer correctly "$P$ stops on $x$" or "$P$ runs for ever on $x$". Build a new program $D$: given a program $P$, it asks $H$ whether $P$ stops when given its own text as input, and then does the opposite — if $H$ says "stops", $D$ loops for ever; if $H$ says "runs for ever", $D$ stops.

Now run $D$ on its own text. If $D$ stops, then $H$ said "$D$ runs for ever" — wrong. If $D$ runs for ever, then $H$ said "$D$ stops" — wrong again. Either way $H$ makes a mistake, so the perfect checker $H$ cannot exist. This is the halting problem, and it is undecidable.

This is the same diagonal trick Cantor used to show that some infinities are bigger than others, and Gödel used to show that no consistent formal system can prove every true statement about whole numbers. It does not say that we can never tell whether a particular program stops — often we can — only that no single program can do it for all programs. Henry Rice later showed that the same holds for every non-trivial question about what programs compute.