Writing correct software is hard and math alone won’t help us (2016)

364 points · 180 comments on HN · read original →

Points and comments are a snapshot, not live.

Computational limits make software correctness fundamentally hard, not just a tooling problem.

The article argues that software correctness faces essential, not just practical, barriers. Gödel's incompleteness theorems and the halting theorem show that no algorithm can decide if any given program terminates or satisfies non-trivial properties. Rice's theorem extends this to any non-trivial property of partial functions. The Busy Beaver theorem gives a quantitative measure: for a 2-symbol Turing machine with just 6 states, the maximum halting steps exceed 7.4 × 10^36534. A 1919-state Turing machine exists whose termination is independent of ZFC set theory, meaning it cannot be proven to halt or not within standard mathematics. Even programs that are provable in principle may require proofs too large to be feasible.

What commenters are saying

Commenters largely agree that formal verification is valuable but not a panacea. Several note the gap between theoretical computer science and practical software engineering, with one citing Dijkstra's quip that "computer science is no more about computers than astronomy is about telescopes." Another camp argues that real-world software must handle probabilistic inputs (e.g., sensors) and that proofs often rest on assumptions that don't hold in practice. A top comment stresses that building verifiable programs requires "real thought and deep insight," not just tools. One commenter connects the self-referential structure of the halting problem to Gödel's incompleteness via the "self-referential probability question" meme.