Can a program analyze arbitrary source code and decide, in finite time, whether it will halt or loop forever? In 1936, Alan Turing proved the answer is no.

The proof is a short exercise in self-reference: you construct a program that uses the hypothetical decider against itself, forcing a contradiction.

Why It Matters

The result draws a hard line on what automated tools can guarantee. Compilers, linters, and static analyzers can catch large classes of bugs, but they can never detect all infinite loops or all unreachable code in arbitrary programs. Detecting whether a given piece of code loops forever is exactly the halting problem, so any tool that claims to catch every such case would need a halting decider, which, as the proof below shows, cannot exist.

Setup

To prove something is impossible, you start by assuming it is possible, and then show the assumption leads to a contradiction.

Let’s assume we managed to write a perfect function, will_halt(program, input). It takes the source code of any program and its input data, analyzes it without executing it, and returns a boolean: true if it halts, false if it loops forever. And will_halt itself never freezes. It always terminates with an answer.

Counter-Engine

To break this, Turing constructed a deliberate contradiction. Let’s call it devious.

devious takes the source code of any program as an argument. It passes that code into our perfect will_halt function, asking a specific question: “What happens if this program is fed its own source code as input?”

Once it gets the answer, devious does the exact opposite:

function devious(program_code) {
    if (will_halt(program_code, program_code)) {
        while (true) { /* loop forever */ }
    } else {
        return; // halt immediately
    }
}

If the predictor says the code will finish, devious spins off into infinity. If the predictor says it will loop, devious immediately returns and stops. It is explicitly engineered to make a liar out of will_halt.

Contradiction

What happens when you pass devious into itself?

devious(devious_code); // where devious_code is devious's own source

Let’s step through what will_halt has to decide inside that call:

  1. If will_halt returns true (“this will halt”), then the if branch runs. devious enters the infinite loop and never halts. The predictor is wrong.
  2. If will_halt returns false (“this will loop forever”), the else branch runs. devious halts immediately. The predictor is wrong again.

Notice what will_halt is actually being asked here. Inside the call devious(devious_code), the line will_halt(devious_code, devious_code) runs. That’s asking: “does devious halt when given its own source as input?” and we have exactly called devious with devious_code as input.

There is no third option. will_halt cannot return true, and it cannot return false. The function is logically impossible to implement.

Conclusion

This isn’t a limitation of our current tools. It’s a theorem. Turing didn’t just find an edge-case bug; he proved that algorithmic prediction of program behavior has a hard, mathematical ceiling. No procedure, static or dynamic, can decide whether an arbitrary program halts.

In practice, this ceiling rarely matters. We build good-enough heuristics (linters, type checkers, bounded model checkers) and accept that “works for all practical inputs” is not the same as “provably correct for all inputs.”