Library / Computational Thinking DPF
Jump to passage
In this reading

Link to current text

Published source confirmed at last check

Source changed 2026-10-03 05:16:27 UTC · snapshot created 2026-10-03 05:17:06 UTC · last check 2026-10-03 05:20:20 UTC

CMP.6:4.4 - Establish what repeated updates imply

Select a progress argument appropriate to the state space and update:

Available structureWhat can be establishedWhat remains to be supplied
A finite candidate set and strict improvement at every accepted changeNo candidate repeats; the procedure reaches a state with no accepted improving change.A feasible way to find or rule out such changes, and a useful bound on the amount of work.
A decreasing nonnegative integer potentialAt most its initial value many decreases of at least one.The potential’s encoded magnitude can be large, and one iteration may be expensive.
A contraction or another quantitative convergence relationA finite error bound after a chosen number of updates.A way to compute the required update and connect that error to the requested result.
A descent estimate with a bounded-below objectiveBounds on accumulated improvement and, under appropriate assumptions, stationarity measures.Convergence to one point or global optimality requires its own additional conditions.

Use MATH.20 for the bound and MATH.21 for the convergence construction when needed. If each step improves but there is no useful stopping guarantee, return that limited procedure or change the method. Equal-value moves need their own cycle handling; strict-improvement reasoning does not cover them.