LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-generatedprecheck pass

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Finite arithmetic schedules terminate, with early failure counted separately

Statement

Fix an initialized finite state and an ordered list of $M \geq 0$ instructions, followed by a specified completion return. Each instruction reads only initialized data and deterministically either produces the next finite state or returns a specified early status in finite time. There are no backward jumps. Then execution terminates at the first early return, if any, or at the completion return, after at most $M$ attempted instructions. A finite nesting of counted loops with bounds fixed by the finite input has the same property whenever unrolling the loops gives such a list.

In particular, consider $d \geq 0$ levels containing $2^{d - ℓ}$ addition instructions at level $ℓ = 1, \dots, d$ , with each addition returning a rounded value or immediate failure. A successful execution attempts exactly $2^{d} - 1$ additions; every execution attempts at most $2^{d} - 1$ . For $d = 0$ there are no additions. These conclusions assert finite execution, not arithmetic success or accuracy.

Facts & Assumptions

Given: the finite ordered instruction list, its initialized state and completion return, and the per-instruction finite-return hypothesis in the Statement.

Proof

1.1givenalgebra

After the first $j$ instructions have completed without an early return, the state needed by instruction $j + 1$ is initialized by hypothesis. That instruction either returns an early status or finishes in finite time. Induction for $j = 0, \dots, M - 1$ therefore reaches an early return or completes all $M$ instructions and the specified completion return. An early return stops before any later instruction, so it is the first one and at most $M$ instructions are attempted. This includes $M = 0$ , when only the completion return is executed.

2.1givenstep 1.1algebra∎

Unroll counted loops in their prescribed order. A loop with zero iterations gives an empty list; a loop with a fixed finite number of iterations concatenates that many finite lists. Induction on the finite nesting depth gives a finite list with the same execution order, so step 1.1 applies. In the addition schedule the number of slots is $S_{d} = \sum_{ℓ = 1}^{d} 2^{d - ℓ}$ . Here $S_{0} = 0$ and $S_{d + 1} = 2 S_{d} + 1$ , whence induction gives $S_{d} = 2^{d} - 1$ . Success visits every slot, while failure visits only an initial segment, proving both counts.

Remarks

The source supplies background on rounded arithmetic and range limitations. The local argument proves the finite-schedule and counting assertions; it does not assume that a primitive operation can run indefinitely while searching for a certificate or a rounded answer.

Used by

Balanced pairwise summation with range-failure status Algorithm
Failure-aware rounded Cholesky factorization Algorithm
Kahan compensated summation with range-failure status Algorithm
Neumaier compensated summation with range-failure status Algorithm
TwoProduct product and residual computation using fused multiply-add Algorithm
A successful natural-cubic tridiagonal Cholesky solve has a certified residual Theorem

Dependency tree · 0 levels

Nothing. This result depends on no other item in the library.

Sources

Driscoll and Braun, Fundamentals of Numerical Computation, floating-point numbers (standard reference, not scraped)