Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

The programs that can be proven are severely limited in power. For one, the tools to prove correctness of programs can't deal with data other than integers[1].

The way this usually works is that the proof is written and the code is then generated from the proof. That code is then incorporated in something larger, which has not been proven correct. Such is the case with algorithms. You can mathematically prove an algorithm correct. You can even write a proof and generate a program from it. Then you still have to use that algorithm and all the code using it can't be proven correct with current methods. That is why you will still have to test your program.

  There are even entire programming languages designed for
  the sole purpose of making formal, mathematical
  verification of programs easier.
Yes, and their practical usefulness is still severely limited.

[1] Of course, in theory this means they can deal with any data; in practice it means they can't.



For one, the tools to prove correctness of programs can't deal with data other than integers.

This is the first time I hear such claim. Which tools are you talking about? The tools I know (Coq) certainly don't have such limitations -- why would they, anyway?


For performance reasons. The SPIN model checker, which is the state of the art in terms of performance, employs only integers.

Has Coq ever been used to solve an actual practical industrial or business problem, either by generating code from a known correct program or by using the Coq model as an oracle to drive automatic testing? If not, then there's your answer: academically useful proof assistants cannot deal with real world data. Proof assistants useful in the real world can only deal with limited data types to be able to achieve their goal.




Consider applying for YC's Fall 2026 batch! Applications are open till July 27.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: