Hoare: Assertions and Termination

A rule and its limit

Hoare’s assignment rule substitutes an expression into an assertion. His iteration rule preserves an invariant while the guard is true and yields the invariant with the negated guard when execution terminates. The paper does not supply a general termination proof.

The selected page also discusses restrictions such as expression side effects. The calculation below removes that complication by stipulation rather than treating every programming language as if it obeyed the same rules.

Sources for this section: [1]

Two original questions

Use unbounded mathematical integers and side-effect-free expressions. First execute x:=x+2, then y:=3*x. Find the weakest starting condition on x that ensures y≥15. Assignments occur in order; the second uses the new x.

Second, take an integer n≥0. Set i=0, s=0. While i<n, execute i:=i+1 followed by s:=s+i. Show that 2s=i(i+1) and 0≤i≤n are preserved. What holds when the loop stops? Supply a separate decreasing quantity proving that it does stop.

Sources for this section: [1]

Reference answer: work backward and forward

For the assignment, 3(x+2)≥15 is equivalent to x≥3. There is no rounding or overflow in the stipulated arithmetic. A fixed-width implementation would need its own bounds.

Initially 2s=i(i+1)=0. If the old value is i, the body adds i+1, so the new doubled sum is i(i+1)+2(i+1)=(i+1)(i+2). The guard and n’s integrality preserve the stated bounds. At exit i=n, so s=n(n+1)/2.

The nonnegative integer n−i decreases by one on every iteration. This separately proves termination in the fixture. Reversing the two body assignments instead sums 0 through n−1; for n=3 it returns 3 rather than 6. Order is part of the program, not a stylistic choice.

Sources for this section: [1]

Return to the research question

The example distinguishes a logical relationship from an execution guarantee. The invariant alone supplies the requested relationship on exit; the decreasing quantity closes a different obligation. Neither step validates an unspecified compiler, finite-word arithmetic or an arbitrary program.

Sources for this section: [1]