Why computers can't predict every program's fate

The prediction problem has to include the program’s input

A program does not simply “stop” or “run forever” in the abstract: its behavior can depend on the data it receives. The formal question is whether a specified program, given a specified input, eventually finishes. A halting checker would be an algorithm that always answers this question correctly for every possible program-and-input pair.

The difficulty is not merely that some programs take a very long time. Waiting longer cannot distinguish a slow program from one that will never finish. The deeper obstacle is that a universal checker can be made to contradict its own answer.

How the contradiction is built

Imagine a checker that accepts a program as data and predicts whether it will finish. A new program can use that checker on a copy of its own instructions. If the checker predicts “finishes,” the new program deliberately loops; if the checker predicts “loops,” it deliberately finishes.

Run this new program on itself. If the checker says it will finish, it loops instead. If the checker says it will loop, it finishes instead. Either prediction is wrong. So the imagined checker cannot exist as an algorithm that handles every possible case.

This is a form of diagonal argument: construct an object that differs from each proposed prediction in the one place where that prediction is supposed to apply. The paradox is not evidence that ordinary computers behave inconsistently. It shows that the promised all-purpose predictor is impossible.

What programmers can still predict

The result does not make program analysis futile. Tools can prove that many particular programs finish, detect many definite loops, or check restricted classes of code. But any method that always gives a correct answer must leave some cases unresolved—or impose limits on which programs it handles.

That boundary matters in practice: a software tool can be highly useful without being able to certify every program. The impossible part is not prediction in general; it is a perfect, automatic answer for every program and input.