Comment

Comment by emillon

This kind of proofs usually are separated in two steps:

- correction: define a loop invariant. Assuming the loop terminates, it will hold when the program exits the loop.

- termination: define a loop variant, something that changes at every iteration. If you can find a variant that is a strictly decreasing sequence of natural numbers (or an increasing, bounded sequence), you've established that the loop terminates.

Once you've done these two steps you know that the program terminates and the invariant holds at the end. (in your case, you won't be able to find a good variant - depending on the floating point semantics you use of course).

parent emillon 10 years ago

No comments yet

Be the first to share your thoughts.

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton