Re:Prediction: AI will make formal verification go mainstream
by kazinator on Wednesday December 17, 2025 @04:25AM
(#46299876)
If you eliminate the odd integers from consideration, you've eliminated an entire class of integers. yet, the set of remaining integers is of the same size as the original.
[ Parent
| on HN ]
Re:Prediction: AI will make formal verification go mainstream
by moi2388 on Wednesday December 17, 2025 @08:02AM
(#46301489)
No, because integers in computing are generally finite.
Re:Prediction: AI will make formal verification go mainstream
by petesergeant on Wednesday December 17, 2025 @04:55AM
(#46300049)
Peak HN gnomism. While the set of possible errors may be infinite, their distribution is not uniform.
Re:Prediction: AI will make formal verification go mainstream
by tmtvl on Wednesday December 17, 2025 @01:06PM
(#46303156)
There cannot be infinite bugs in a limited program.
Re:Prediction: AI will make formal verification go mainstream
by Hercuros on Wednesday December 17, 2025 @04:04PM
(#46305480)
How do you count how many bugs a program has? If I replace the Clang code base by a program that always outputs a binary that prints hello world, how many bugs is that? Or if I replace it with a program that exits immediately?
Maybe another example is compiler optimisations: if we say that an optimising compiler is correct if it outputs the most efficient (in number of executed CPU instructions) output program for the every input program, then every optimising compiler is buggy. You can always make it less buggy by making more of the outputs correct, but you can never satisfy the specification on ALL inputs because of undecidability.
Re:Prediction: AI will make formal verification go mainstream
by kazinator on Wednesday December 17, 2025 @02:36PM
(#46304423)
Programs are not limited; the number of Turing machines is countably infinite.
When you say things like "eliminate a class of bugs", that is played out in the abstraction: an infinite subset of that infinity of machines is eliminated, leaving an infinity.
How you then sample from that infinity in order to have something which fits on your actual machine is a separate question.
Re:Prediction: AI will make formal verification go mainstream
by gls2ro on Wednesday December 17, 2025 @01:39PM
(#46303613)
Because the number of state where a program can be is so huge (when you consider everything that can influence how a program runs and the context where and when it runs) it is for the current computation power practically infinite but yes it is theoretically finite and can even be calculated.