Kolmogorov Complexity Justifies Software Engineering Heuristics
Ann Quiroz Gates, Владик Крейнович, Luc Longpré · scholarworks - UTEP (The University of Texas at El Paso) · 1998
Many software testing techniques are heuristic, so the "clean bill of health" produced by such a technique does not guarantee that the program is actually correct. In this paper, we show that several heuristic techniques for software testing that have been developed in software engineering can be rigorously justified. In this justification, we use Kolmogorov complexity to formalize the terms "simple" and "random" that these techniques use. The successful formalization of simple heuristics is a good indication that Kolmogorov complexity may be useful in formalizing more complicated heuristics as well. Formulation of the problem. It is desirable to have programs that are 100% justified. Such programs exist, but they are extremely rare. Most programs do not use only mathematically justified methods of solving equations etc., they also use heuristic and semi-heuristic methods and ideas, i.e., methods that are not 100% justified. For such not-100%-justified programs, we must use testing to...