Why Writing Correct Software Is Hard

The article argues that writing correct software is fundamentally difficult because of inherent limits in computability and complexity theory, not merely a lack of better tools. It traces the problem to David Hilbert’s early-20th-century program to formalize mathematics and decide every statement algorithmically, a goal later undermined by results showing that complete understanding of all program properties is impossible. The author, drawing on his experience formally specifying and verifying an upcoming revamped version of Galaxy and prior work with Quasar, contends that correctness carries an unavoidable cost akin to reducing entropy. The piece aggregates proofs and references to explain why programs and complete understanding are at odds, and it pushes back on online claims that the right tools make correctness easy. It matters because it sets expectations for verification efforts: tools can help, but cannot eliminate the underlying difficulty. What to watch next is how the revamped Galaxy verification work proceeds and whether it bears out the article’s thesis in practice.