Quick Answer: Writing correct software is hard because proving a program does what you intend requires understanding its full behavior, and the foundations of computation show that no general procedure can do this for every program. The halting problem, Rice's theorem, and Gödel's incompleteness results set hard limits. Verification tools work anyway, but they succeed by restricting what they check, not by removing those limits.

Most people who build software have felt this. A bug that only appears under one specific timing, an edge case nobody thought to test, a function that is "obviously correct" until it isn't. Then you hear someone claim that with the right formal methods, correctness is simply a matter of effort. Pron's essay, discussed on Hacker News, argues that this claim misses something fundamental. The difficulty isn't a gap in our tools. It's built into the mathematics of computation.

Hilbert's Dream and Why It Died

In the early twentieth century, David Hilbert wanted to formalize all of mathematics. He wanted three things: a proof that the formal system was consistent, a proof that it was complete, and a decision procedure (the Entscheidungsproblem) that could determine whether any statement was a theorem. His 1930 Königsberg lecture declared, "We must know, we shall know."

That optimism didn't survive the decade. Kurt Gödel's incompleteness results, announced in 1930, took apart the first two pillars. In 1936, Alonzo Church and Alan Turing dealt with the third by proving the halting theorem. Hilbert's hope that anything formally reasoned about could be fully understood turned out to be false.

This matters for software because a program is a formal object. If its behavior can't be fully understood in general, correctness can't be guaranteed in general either. Here's where most discussions of software correctness stop, and where they should start.

The Halting Problem: You Can't Check Every Program

The halting theorem says there is no algorithm that decides whether an arbitrary program will terminate. The proof uses self-reference. Assume a decider H exists. Build a program G that asks H what G will do when given itself, then does the opposite. The contradiction means H can't exist.

For a developer, the practical consequence is blunt. A static analyzer that promises to find every infinite loop in every program you'll ever write cannot exist. Any tool that claims otherwise must be deciding a narrower question, or it's wrong on some inputs.

Reachability has the same problem. No program can determine whether a given machine ever reaches a given state from a set of initial states. This is the formal version of asking "can this bad state ever happen?" and it's undecidable in general. That question sits at the heart of safety verification.

Rice's Theorem: Almost Every Interesting Question Is Undecidable

Rice's theorem generalizes the problem. For any non-trivial property of what a program computes, no algorithm can decide whether an arbitrary program has that property. Take the question "does this function always return the square of its input?" No algorithm can answer it for every program.

Here's the counter-intuitive part. Many engineers assume that if they only ask about specific behavior ("does this sorting function return a sorted list?"), the question must be easier. Rice's theorem says the difficulty doesn't go away when you narrow the question. It only goes away when you restrict the programs you're willing to analyze.

That's the trade-off hidden in every verification tool. Model checkers like those built on TLA+ explore finite state spaces. Type systems reject programs that might be correct because they can't prove otherwise. Languages like Dafny require you to write invariants that make verification tractable. Each one picks a decidable slice of the problem and gives up the rest.

Busy Beaver: Complexity Outruns Any Computable Function

The essay's most striking result is what it calls the "Busy Beaver theorem." Define f(n) as the maximum number of steps a halting Turing machine with n control states can take before halting. Since there are finitely many machines of size n, f(n) is well-defined. But f is non-computable. If it were, you could decide halting for any machine of size n by running it for f(n) steps.

The same argument applies to proofs. Let g(n) be the maximum size of the shortest termination proof across all terminating machines of size n. g is non-computable too. Any computable function that bounds f or g from above can be used to decide halting, which the halting theorem rules out.

The numbers get big fast. The source notes that for n = 6 with a 2-symbol alphabet, f(6) is greater than 7.4 × 10^36534. You won't ever compute that value, and no algorithm will reliably predict proof sizes for arbitrary machines of this kind. That's the quantitative face of the difficulty: the cost of verifying a program can grow faster than any function you could write down to estimate it.

Here's what this means in practice. A verification effort is not just "more work for bigger programs." For some programs, the proof simply has no bound you can plan around.

Some Small Programs Can't Be Proven to Behave at All

Gödel's second incompleteness theorem gives an even sharper result. A consistent formal system can't prove its own consistency. Mathematicians use ZFC (Zermelo-Fraenkel set theory with the axiom of choice) as the foundation for most of their work. Build a program that enumerates ZFC theorems and halts only if it finds a contradiction. If ZFC is consistent, the program runs forever. But you can't prove that inside ZFC.

This isn't just a thought experiment. Adam Yedidiya and Scott Aaronson published a program along these lines in 2016, and Stefan O'Rear quickly produced a Turing machine with 1,919 control states whose termination is independent of ZFC. The source compares its size to a Python program of roughly 100 to 200 lines.

Most people stop here, but this is the part that should change how you think about your next code review. You don't need a huge codebase to hit the limits of mathematical proof. Some very small programs have behavior that no proof system you can name will settle. Most production code isn't adversarially designed like this, so the result doesn't mean your service is unverifiable. It means that "any program can be verified, given enough effort" is false as a universal claim.

Worst-Case Limits vs. Practical Verification

Here's the nuance a responsible expert has to acknowledge. These theorems describe worst-case behavior over all programs. They don't say that verifying your particular program is impossible. Real systems are verified every day, and some are verified in extraordinary depth. The seL4 microkernel, for example, has a machine-checked proof of functional correctness built in Isabelle/HOL. That effort is enormous, but it exists because the team designed the kernel and its proof together.

The lesson is about where the cost lands. Verification is cheap when you control the program's structure, choose a restricted property, and accept an abstraction. It becomes expensive or impossible when you need to reason about arbitrary code, unbounded loops, or behavior you didn't design for.

That's why "the right tools make correctness easy" is incomplete. Tools make correctness achievable for a chosen slice. They don't dissolve the limits. Pron's essay puts the cost of correctness in the same category as the energy cost of reducing entropy: a consequence of the natural laws of computation, not a shortcoming of current engineers.

Comparing Approaches: What Each One Actually Guarantees

ApproachWhat it guaranteesTypical costExample tools
TestingCorrectness on tested inputs onlyLow to moderate; coverage gaps are structuralJUnit, pytest, QuickCheck
Model checkingExhaustive check of a finite modelModerate; state-space explosion on large systemsTLA+, SPIN, TLC
Type systemsAbsence of certain error classes, by constructionLow at runtime; restrictive for the programmerRust borrow checker, Haskell
Deductive proof assistantsMachine-checked proof of stated propertiesHigh; proofs often dwarf the code they verifyCoq, Isabelle/HOL, Lean
Contract-based verificationVerified pre/postconditions for annotated codeModerate; requires writing specificationsDafny, Frama-C, SPARK Ada

Use testing when you need fast feedback and can tolerate gaps. Use model checking when the risk is in the protocol or concurrency design, not the individual function. Use proof assistants when the cost of failure justifies months of expert effort. Each row is a trade-off, and none is free of the theorems above.

What You Can Do Differently Tomorrow

Accept that you're choosing a decidable slice, and be explicit about it. Write down the property you're verifying and the assumptions it relies on. If you can't state the assumptions, you don't know what your verification covers.

Pick the verification method for the risk, not the trend. A state machine in a payment flow probably deserves model checking. A string parser may need fuzzing and property tests more than a theorem prover. Ask what failure would cost, then match the tool to that cost.

Keep your programs small and structured. The theorems say complexity can explode, so reducing the surface you need to reason about is the most reliable way to keep verification tractable.

Frequently Asked Questions

What is the halting problem in simple terms?

The halting problem asks whether a program will eventually stop or run forever when given some input. Alan Turing proved in 1936 that no general algorithm can answer this for every possible program. That's why no tool can guarantee that all your code terminates.

How can I verify my software is correct?

Start by writing down the exact property you care about, such as "this queue never drops messages." Then choose a method that fits the risk: property-based testing for functions, TLA+ for protocols, or a contract language like Dafny for critical logic. Each method covers a specific slice of behavior, so state your assumptions clearly.

Why can't formal verification prove every program correct?

Formal verification tools work by restricting the programs or properties they accept. Rice's theorem shows that for any non-trivial property of program behavior, no algorithm can decide it for all programs. Verification succeeds in practice by choosing decidable subsets, not by solving the general problem.

Are there programs that can never be proven to terminate?

Yes. Using Gödel's second incompleteness theorem, researchers have built small Turing machines whose termination can't be proven within ZFC set theory. O'Rear's machine with 1,919 control states is one example. Most real software isn't built this way, but the result shows the limits are not only about program size.

Is software correctness impossible to achieve?

No. Correctness is achievable for specific properties in well-scoped systems, as projects like the seL4 microkernel demonstrate. What's impossible is a universal guarantee that any arbitrary program behaves as intended. Treat correctness as a set of bounded, explicit claims rather than a single yes-or-no property.

Writing correct software is hard because the mathematics of computation makes complete understanding impossible in general, not because engineers are careless. The practical takeaway is to pick a verification method that matches your specific risk, state its assumptions, and keep the code you need to reason about small. Try this week: choose one critical function or protocol in your codebase, write down the single property it must satisfy, and check whether your current tests actually cover it. Pass this to someone wrestling with flaky behavior they can't reproduce, because the gap between what you tested and what you claimed is where correctness usually breaks.