ExampleConstruction: AI-generatedVerification: AI-adaptedPipeline-generated

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.

Smn specializes a two argument index

Example

Take the addition derivation $A (a, 0) = a$ , $A (a, y + 1) = S (A (a, y))$ and apply the finite syntax compiler from the normal-form construction (available through specialization). Let w be its emitted machine word and let $e = 2^{∣ w ∣} - 1 + val (w)$ be its length-lex index. This specifies an actual compiled index, without pretending it has a particular short decimal value. Concretely its routine parses two numeral blocks, stores the first in an accumulator and the second in a counter, increments the accumulator and decrements the counter until the latter is zero, then writes the accumulator as output. Each binary decrement changes trailing zeros to ones and the preceding one to zero and removes a newly redundant leading zero, retaining the single word 0 for zero.

Set $q = s_{1}^{1} (e, 3)$ . Then q computes $y \mapsto 3 + y$ ; in particular $φ_{q} (0) = 3$ and $φ_{q} (4) = 7$ .

Facts & Assumptions

Given: The explicitly specified addition routine, compiled with the literal finite-state routine convention of the preceding normal-form and specialization constructions. A fixed ordering of the emitted states is part of that compiler, not a claim that all compilers give the same e.

[F1]

Specialization prepends stored parameters and preserves partial-function values and domains (Smn for the fixed acceptable numbering).

[F2]

Addition is given by primitive recursion and canonical numeral operations are PR (Fixed coding primitive recursive arithmetic and sequences).

Verification

1.1

After j loop iterations, the accumulator is $a + j$ and the counter is $y - j$ , for $0 \leq j \leq y$ : initially this is the parsed input, and one increment/decrement preserves the formula. The counter reaches zero after exactly y iterations, giving output $a + y$ . At y=0 the loop is skipped. These are the addition recursion and its finite numeral routines in F2, so the compiled index e has the advertised total binary function.

F2given

2.1

Specialization F1 writes the stored numeral $bin (3) = 11$ before the input numeral and sends the two-entry tuple to e. For y=0 the arity header is 110, the block for 11 is 11011 and the block for 0 is 100, so the exact grouped encoding is $110 11011 100$ . For y=4 it is $110 11011 1110100$ , since the block for 100 is $1110 100$ . The first calculation leaves accumulator 3 unchanged and outputs 11; the second has accumulator values $3, 4, 5, 6, 7$ and counter values $4, 3, 2, 1, 0$ , outputting 111. Thus canonical input numerals 0 and 100 produce 11 and 111 respectively, and F1 gives the asserted equality for every y.

step 1.1F1∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

5 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Gallier Theorem 3.1; local worked specialization (standard reference, not scraped)