Rippling: Meta-level Guidance for Mathematical Reasoning

Chapter 5: The Scope and Limitations of Rippling

Overview

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 .

5.1 Hit: Bi-Directionality in List Reversal

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:

(5.2)

(5.3)

Wave-rules:

(5.4)

(5.5)

(5.6)

(5.7)

(5.8)


Figure 5.1: Bi-directionality in a list-reversal example. The rippling proof starts with the applications of the...

UNLIMITED FREE
ACCESS
TO THE WORLD'S BEST IDEAS

SUBMIT
Already a GlobalSpec user? Log in.

This is embarrasing...

An error occurred while processing the form. Please try again in a few minutes.

Customize Your GlobalSpec Experience

Category: Standards and Technical Documents
Finish!
Privacy Policy

This is embarrasing...

An error occurred while processing the form. Please try again in a few minutes.