Induction as the basis for program verification

摘要

We will consider the inductive mechanisms in five techniques for verifying iterative/recursive program structures: inductive assertion, predicate transformers, subgoal induction, computation induction, structural induction. We will discover that all five techniques can be justified by a single theorem about inductive proof techniques. We will also show that all five techniques face the problem of finding properties that will carry an induction.

Such properties are called inductive sets. We will see that the inductive sets of the five techniques are easily related to one another and that a program proof by any of the techniques can be easily converted to a proof by any of the other techniques. Our conclusion is that computer programs simply are inductive definitions of the functions they compute. Induction is the only method by which they can be proved. The problems of induction are therefore unavoidable.