# The Fundamental Difficulty of Software Correctness Why mathematical limits and computational theory make perfect software verification an impossible goal. - **Source:** [Hacker News (news.ycombinator.com)](https://brifing.si/source/13c923cd-6d99-442b-9b8b-1181f4d8cd91) - **Published:** 2026-11-12 - **Topic:** [technology](https://brifing.si/c/technology) - **Original article:** - **On Brifing:** https://brifing.si/s/05069b77-1503-4fa4-adb1-fbb59a4d45a5 ## The Illusion of Perfect Software Many developers believe that with the right tools, achieving perfect software correctness is a simple task. However, theoretical computer science suggests otherwise. The cost of ensuring a program is entirely correct is not just a resource issue, but a fundamental constraint imposed by the natural laws of computation that cannot be avoided. ## Hilbert's Failed Formalization Program In the early 20th century, David Hilbert aimed to formalize all mathematics, seeking an algorithm to determine the truth of any statement. He famously declared that we must know and shall know. This ambitious goal was dismantled in 1931 when Kurt Gödel published his incompleteness theorems, proving that some statements remain unprovable. ## The Halting Theorem Explained Proven by Alan Turing and Alonzo Church in 1936, the halting theorem is foundational to computer science. It states that no algorithm can determine if any arbitrary program will eventually terminate or run forever. This proof uses diagonalization, a self-referential technique that creates a logical contradiction if such a decider existed. ## Implications for Software Verification The halting theorem directly impacts software verification by proving that reachability is undecidable. There is no general program that can determine if a specific state will ever be reached by another program. This means we cannot build a universal tool to verify that all software will behave exactly as intended. ## Rice's Theorem and Functionality Rice's Theorem extends these limitations, stating that no algorithm can decide any non-trivial property of partial functions computed by programs. For instance, you cannot create a universal tool to verify if a program's output is always the square of its input, as this is undecidable via reduction from the halting problem. ## The Busy Beaver Function The Busy Beaver function, f(n), defines the maximum steps a halting Turing machine with n states can take. This function is non-computable, meaning it grows faster than any computable function. It provides a quantitative measure of the inherent complexity involved in analyzing program behavior, whether viewed statically or during runtime execution. ## Static Proofs are Non-Computable Similar to dynamic execution, the static analysis of program termination is also non-computable. The function g(n), representing the maximum size of a minimal proof of termination for a machine of size n, is non-computable. This confirms that the difficulty of proving termination scales beyond the reach of any computable decision procedure. ## Practical Limits of Verification While we cannot compute f(n) for all n, we can calculate lower bounds for small values. For a 6-state Turing machine, the value is approximately 7.4 times 10 to the power of 36534. These astronomical numbers illustrate why exhaustive verification is physically and mathematically impossible for even relatively simple, small programs. ## Independence from ZFC Axioms Gödel’s second incompleteness theorem implies that some programs are independent of ZFC set theory. Researchers like Stefan O’Rear have created Turing machines with only 1919 control states whose termination cannot be proven within ZFC. These programs are mathematically indeterminate, meaning their behavior is beyond the reach of formal proof systems. ## Physical Nature of Computation Alan Turing emphasized that computation is tied to physical processes, not just abstract mathematical objects. The Church-Turing thesis suggests that any realizable physical process can be simulated by universal computational models. This connection reinforces why the halting problem is a central, unavoidable limitation for all physical computers we build today. ## Computer Science Versus Mathematics Computer science is largely concerned with what lies outside the circle of provable mathematics. Many programs are only provable in theory, but not feasibly provable in practice. This distinction highlights that computer science is not merely a subset of math, as it deals with physical constraints and non-computable, real-world behaviors. ## The Reality of Software Complexity Ultimately, programs are fundamentally at odds with full understanding and correctness. While tools assist in reducing errors, the theoretical limits established by Turing and Gödel remain. Developers must accept that perfect verification is an unreachable ideal, as the complexity of software behavior inherently exceeds our capacity for complete formal proof. ## Sources covering this story - https://pron.github.io/posts/correctness-and-complexity — --- _Summary written by Brifing from the original reporting. Copyright in the original article belongs to its publisher; read the full piece at the link above._