Rippling: Meta-level Guidance for Mathematical Reasoning

In this chapter we survey applications of rippling, both within and outwith induction, successful and unsuccessful, by a wide variety of researchers. We start with examples where rippling has successfully guided a proof attempt and reduced the amount of search. We will see that rippling is both applicable and successful in a surprisingly wide variety of situations.
However, we also survey some failures of rippling. The notion of failure is a fuzzy one. In many of the cases discussed, we speculate on extensions of rippling that might turn failure into success. We also give examples of where proof critics can analyze the failure, and suggest a successful patch to the proof attempt.
Section headers of successful examples are preceded by Hit and unsuccessful ones by Miss .
The following rather artificial example was constructed to illustrate the ability of rippling to use rewrite rules in both orientations while still guaranteeing termination:
The details of the step case of the inductive proof can be found in Figure 5.1. Note that rewrite rules (5.7) and (5.8) are the same equation oriented in opposite directions. They are applied at steps (5.3) and (5.2), respectively.
| Given: | ||||||
| qrev( qrev(tl, L), [ ])= rev(L) <> rev(rev(tl)) | ||||||
| Goal and ripple: | ||||||
|
| ||||||
|
| ||||||
| Wave-rules: | ||||||
|
| ||||||
|
| ||||||
|
| ||||||
|
| ||||||
|
|