Reply to Message
Unreachable intent...
As soon as we have defined a machine that is as powerful as a Turing machine to be complete enough and solve problems based on algorithms using those capabilities, the system becomes complex enough that the problem it is spposed to solve becomes provably correct. If it was, the system would be incomplete and limited to a few ranges of problems and solutions, or it won't find any solution in a finite time over a finite machine. It is even sometimes impossible to predict that the result will be incorrect. (there's a mathematical proof of this...)
One common example: it is most often impossible to determine if the program will terminate, if it contains loops with conditional breaks, because it is alsmost impossible to determine tha this condition will be satisfied, except in very few cases (such as counted loops where the loop counter is warrantied of strictly *never* being modified outside of the surrounding loop control : this is a frequent case in almost all softwares, but that does not cover many other cases, less frequent, but still present in almost all softwares).
So to solve this issue, one has to find a definition of what is considered a "correct" result, in order to reduce the search space in a model with lower complexity, hiding details that are unsolvable. In many softwares, the solution exposed in its implementation is not based on a proof, impossible to assert, but on an heuristic that produces an approximatively correct solution in a finite time (independantly of its optimisation). So instead of prooving that the result you get is correct, you can just proove that the software correctly implements the heuristic (but frequently without even knowing the level of accuracy, except for some subclasses of the problems this heuristic can solve, that are far below expectations).
So what can a program verifier do ? Basically, it will try to look for uncertainties, missing assertions in the problem description or in its environment. And the software could implement, in places where it is impossible to determine that it will terminate its computation, some "watchdog" that will limit the computations to some "reasonnable" counts of passes through the atomic check, in order to decide to abort the process prematurely in order to return "no solution in a reasonnable time, the problem is too generic to be currently solvable with enough accuracy without a better heuristic implementation".
The art of programming is not really in implementing algorithms, but really into designing the heuristics, and proving that it can solve a useful subset of the exposed problems: with a better heuristic, you may be able to solve more problems, but not the full set of problems initially expected: in other words, you simplify the problem, i.e. you modify it ! The good question is if a solution found with this heuristic is also a correct solution for the unmodified problem... And here again, this last question is not solvable in a reasonable time, for the generic case !
Of course, mathematics can help, but mathematics have already proven the existence of apparently "simple" problems that have unknown number of solutions... (We call these problems "conjectures", because it is also impossible to define them as axiomes without being sure that the augmented reasonment model is provably not self-contradicting ; as long as we won't have found a demonstration, the problem will remain unknown, but there are also mathematical proofs that it is both impossible to find a demonstration of the conjecture, and a proof that it is not self-contradictory so that the system augmented with the axiome becomes completely empty).
Some examples : look for "NP-complete" problems... (does this algorithm terminate and finds the solution or prooves that it has no solution in a polynomial time, instead of a ??? much worse ??? combinatorial time ?).
But we can sometimes proove that some problems are equivalent to some already wellknown NP-complete problems (about 18 of them have been found, possibly a few more now, and their formulation is desesperately simple compared to the heavy implications about their solvability).
One common example: it is most often impossible to determine if the program will terminate, if it contains loops with conditional breaks, because it is alsmost impossible to determine tha this condition will be satisfied, except in very few cases (such as counted loops where the loop counter is warrantied of strictly *never* being modified outside of the surrounding loop control : this is a frequent case in almost all softwares, but that does not cover many other cases, less frequent, but still present in almost all softwares).
So to solve this issue, one has to find a definition of what is considered a "correct" result, in order to reduce the search space in a model with lower complexity, hiding details that are unsolvable. In many softwares, the solution exposed in its implementation is not based on a proof, impossible to assert, but on an heuristic that produces an approximatively correct solution in a finite time (independantly of its optimisation). So instead of prooving that the result you get is correct, you can just proove that the software correctly implements the heuristic (but frequently without even knowing the level of accuracy, except for some subclasses of the problems this heuristic can solve, that are far below expectations).
So what can a program verifier do ? Basically, it will try to look for uncertainties, missing assertions in the problem description or in its environment. And the software could implement, in places where it is impossible to determine that it will terminate its computation, some "watchdog" that will limit the computations to some "reasonnable" counts of passes through the atomic check, in order to decide to abort the process prematurely in order to return "no solution in a reasonnable time, the problem is too generic to be currently solvable with enough accuracy without a better heuristic implementation".
The art of programming is not really in implementing algorithms, but really into designing the heuristics, and proving that it can solve a useful subset of the exposed problems: with a better heuristic, you may be able to solve more problems, but not the full set of problems initially expected: in other words, you simplify the problem, i.e. you modify it ! The good question is if a solution found with this heuristic is also a correct solution for the unmodified problem... And here again, this last question is not solvable in a reasonable time, for the generic case !
Of course, mathematics can help, but mathematics have already proven the existence of apparently "simple" problems that have unknown number of solutions... (We call these problems "conjectures", because it is also impossible to define them as axiomes without being sure that the augmented reasonment model is provably not self-contradicting ; as long as we won't have found a demonstration, the problem will remain unknown, but there are also mathematical proofs that it is both impossible to find a demonstration of the conjecture, and a proof that it is not self-contradictory so that the system augmented with the axiome becomes completely empty).
Some examples : look for "NP-complete" problems... (does this algorithm terminate and finds the solution or prooves that it has no solution in a polynomial time, instead of a ??? much worse ??? combinatorial time ?).
But we can sometimes proove that some problems are equivalent to some already wellknown NP-complete problems (about 18 of them have been found, possibly a few more now, and their formulation is desesperately simple compared to the heavy implications about their solvability).
Posted by PhilippeV
31st May 2011
