Source lean/finite-model-contract.md
# Certified finite computationThe reviewed definitions are in `Determinize/Spec/FiniteModel/`. Graph construction,rational solving, and external certificate checking share those definitions.Implementation details and correctness proofs live in `Proof/FiniteModel/`.## Model and observablesA `Model` has a nonempty finite state space, initial state, rational nonnegativetransition rows summing to one, and states classified as transient, returned witha rational value, or rejected. Evaluation stops at either terminal kind.`outputWithin n s` records the output law reached within `n` transitions;`outputMeasure` is its increasing supremum. Rejection and divergence contributeno output. Finitely many terminal values ensure finite output moments even whenthe chain can diverge.`OutputStatistics.Matches` states exact return mass and first and second outputmoments. Conditional mean and variance divide by return mass; the executableaccessors return `none` at mass zero.`Termination.lean` defines rejection probability by marking rejected states asreturned and discarding successful returns. Divergence probability is the infimumof finite-depth survival probabilities. `Theorems.finite_mass_balance` states that return,rejection, and divergence probabilities sum to one. `TerminationStatistics.Matches`relates the three reported rationals to these probabilities. This distinction isfor the finite model: the core paper semantics counts rejection among executionsthat do not return.## Exact execution boundaryThe exact machine uses rational arithmetic and structural state equality.Bernoulli and discrete samples have finite successors. Primitive means arerational on rational arguments. Residual stochastic continuous and Poisson callsare unsupported, including when nested inside a mean site's operands.Arity and domains are checked; division by zero fails. Encountered nonnumericfinal values and unsupported operations fail explicitly.Functions, recursion, pairs, sums, and lists may occur internally. Structuralexploration can identify finite cycles but does not abstract infinite statespaces. Continuous distributions require an explicit finite approximationbefore exploration unless determinization eliminates them. No discretizationerror theorem is claimed.## Graph construction and correspondence`Finite.explore source subject limits` returns either a complete candidate with`Candidate.ReplayValid source subject`, an incomplete result, or a failure.The builder maintains correspondence between its state array and lookup map,completed rows, and successor coverage. It proves row weights by aggregating alloutcomes for each destination. Hash collisions preserve correctness. The normalexport path consumes this proof directly and does not replay the graph.The candidate records graph data. The independently supplied source and subjectselect the program: either the resolved core source or its Lean determinization.`replay_matches` proves `Model.Matches`, which states paper domain safety andequality of complete unbounded output laws. No typing or termination premise isneeded for this finite-model correspondence.External graph replay validates:- Initial-state alignment, source scope, and dimensions.- Every actual exact-machine step and terminal classification.- Every positive-probability successor and its exact transition weight.- Distinct valid edge indices, positive weights, normalized rows, and absorbing  terminal rows.Portable replay supplies successor indices. Lean checks these against actualsuccessors, then groups probability mass by destination index. Equal state labelsare allowed: the replay proof does not require injectivity or fingerprints. Sparserow checks establish zero weights at absent destinations as well as the weights ofstored edges. Native exploration still deduplicates states as an optimization.Extra valid states, including duplicate labels, are allowed in portable replay.All certificate obligations cover everystored state, including unreachable states.## Why replay implies paper correspondenceThe internal proof modules establish the following chain:- `Substitution`, `Reification`, and `Initial` interpret closures and continuation  stacks as paper expressions and prove initial program alignment. Missing  environment entries map to rejection only in this total internal representation;  replay safety excludes reachable failed lookups.- `Reduction`, `Administrative`, and `Contexts` connect ordinary operations and  contexts to paper reduction. Dropping a stack on rejection preserves zero output  and safety even though paper rejection retains its context.- `Sampling` and `MeasureLaws` identify full primitive measures, finite continuation  sums, and almost-everywhere safety on positive-weight outcomes. Measurability  comes from the existing paper kernel construction.- `Invariants` proves that reachable sampling frames have the required arity.- `Progress` bounds consecutive bookkeeping transitions by a decreasing natural  number. Bookkeeping includes value construction, operand sequencing, and  rejection. Sampling and application transitions are excluded, allowing recursion  to diverge through paper reductions.- `Local`, `Transition`, and `Continuation` classify every successful machine step.- `Execution` proves safety, both finite-horizon comparisons, and unbounded  output-law equality. It accounts for differing numbers of machine and paper steps.- `Graph` regroups exact successor weights using coverage and unique states,  identifying finite and unbounded graph output with machine output.- `Soundness.replay_matches` composes these results without additional typing,  termination, absorption, or integrability premises.## Boundary analysis and value equationsTerminal reachability computes a closed region D from which no terminal stateis reachable. `cut_outputMeasure` proves that replacing D by zero-output terminalstates preserves the entire output law. For each remaining transient state, achosen positive edge of strictly smaller natural rank witnesses a route to theboundary. Other edges may loop or increase rank.`paths_unique` proves uniqueness of the terminal-value equations: a maximumabsolute difference between two solutions propagates along the chosen edges andreaches a zero boundary. This avoids a numerical absorption bound. The analyzerand path constructor return proofs on success; neither claims a separatecompleteness theorem about its implementation.`MomentCertificate` contains D, ranks, chosen successors, and rational valuevectors for return mass and first and second moments. `checkStatistics` checksclosedness, descending edges, and all equations against the original model.`momentCertificate_sound` relates them to its output law. Terminal relabellingand `query_sound` share the proof across observables.`TerminationCertificate` adds a rejection vector, using the same D and paths.The rejection query is formed before cutting off D, so a divergent state cannotbe counted as rejection. `terminationCertificate_sound` proves rejectionprobability and derives divergence from the mass-balance theorem.The verified internal route uses `solveValues` and the proved Gaussian eliminationalgorithm, retaining equation proofs without checking the solutions afterward.`solveStatistics` and `solveTermination` share boundary evidence. Separate right-handsides currently use separate elimination runs.## Portable files and Storm`--export PREFIX` writes raw `.candidate.lean`, standalone `.replay.lean`, andStorm transition, label, and positive/negative reward files. `--result PREFIX`adds `.result.json` and `.result.lean`. Portable Lean files use `decide +kernel`and export axiom reports. They validate saved data rather than rerun explorationand elimination. Each state has a separate kernel proof, assembled through achecked proof table. Moment and rejection equations sum over sparse edges; theirproofs imply the full matrix equations. These checks can cost more than nativeexecution.Every result certificate, from either backend and in either mode, ends with`printedStatistics`. It states `(⟨q, m₁, m₂⟩ : OutputStatistics).Matches (bigStepMeasure(checkedSubject.program checkedSource))`, where `q`, `m₁` and `m₂` are the reported return massand first and second moments as rational literals. Its statement names only `Spec` definitions,`checkedSource` and `checkedSubject`, whose bodies are literals. The proof combines`outputStatistics` with an equation between the certificate's `statistics` and the literals,checked by `decide +kernel`. When the return mass is positive, `printedConditionalMoments`states `returnedExpectation` and `returnedVariance` of the program as literals; it follows from`printedStatistics` by `statistics_returned_moments`.The Storm encoding redirects each terminal to a synthetic zero-reward sink,paying its output reward once. The adapter adds D to the reward-until-target set;original terminals remain outside that target so their reward is paid. It asksStorm for every state's exact rational value, removes the synthetic sink onlyafter checking its dimension and zero value, and writes `.storm.lean`.Positive and negative parts are queried separately for signed first moments.Return, rejection, and second moments use nonnegative reward vectors.The checker binds Storm's vectors to the original Lean graph and its requestedsource/subject. Incorrect transitions, state ordering, rewards, boundary analysis,or rational conversion cannot establish a false equation certificate. The adapternever invokes our solver by default; `--compare` enables a differential check.The result report marks `kernel_checked` only after Lean accepts the certificateand reports that its output-statistics, termination-probability, conditional-variance,reported-statistics and printed-statistics theorems use only `propext`, `Classical.choice`,and `Quot.sound`.## Limits and remaining boundariesExploration limits state count, edge count, and serialized size per state. Sizeis checked after construction and is not a memory bound. An incomplete graphnever becomes a certificate. Computational failures preserve prior exports;filesystem write failures can leave partial output files. Dense solving defaultsto 256 states; Storm uses the exploration limit instead. Subprocess timeoutsbound adapter stages.Parsing and desugaring are unverified. The theorem names the resolved coreprogram rather than the original source bytes. Floating-point sampling is notproved to implement the real-valued semantics. A determinized-program certificatedoes not discharge the source safety and integrability premises needed totransfer its moments back to the source. No approximation theorem connects auser-chosen discretization to a continuous program.## Additive output modelsThe additive backend is the default; `--no-additive` selects the plain one.Normalization extracts the maximal outer suffix of already evaluated numeric-leftaddition frames, sums their constants into the transition reward, and retains onezero-addition frame as a numeric check.Computed and random left operands are evaluated normally before extraction.Other frames, values and environments remain concrete. Right-hand-side folding,multiplication and accumulator abstraction are outside this implementation.An edge reward translates successful outputs. It contributes nothing on rejectedor divergent executions. Thus this is not unconditional accumulated path reward:with return mass p, first moment m and second moment s at the successor, an edgewith reward r contributes p, m+r*p and s+2*r*m+r²*p respectively, weighted by itsprobability. Distinct rewards to the same target remain distinct in these sums.Storm uses their aggregated probabilities for its controller and solves thesuccessive moment right-hand sides, splitting signed right-hand sides intopositive and negative reward queries.`Spec/RewardModel/Model.lean` defines the full successful-output law and `Matches`requires both source `DomainSafe` and equality of that law. `ResultMatches` addsthe common `OutputStatistics.Matches` contract: finite measure, square integrability,and the exact mass and first/second moments. First integrability is derived fromthat contract, and both backends share the same conditional-variance theorem. Local replay is checked againstthe source and selected subject. Exported certificates prove `modelMatches`,`checkedResult`, `integrability`, `outputStatistics` and `conditionalVariance`, and end with`printedStatistics`.The `terminationProbabilities` theorem concerns the probability controller;separate first-hit source rejection/divergence correspondence is not asserted.`integrableMoments` proves `Model.IntegrableMoments` for every finite rewardmodel, without a solution certificate, termination premise, or supplied momentbounds. The proof constructs a closed divergence boundary and descending paths,proves the remaining boundary-value operator is invertible and preservesnonnegativity, and derives finite absolute first/second moment bounds internally.The bounds therefore require no additional runtime solves or certificate vectors.`Theorems.finite_reward_integrability` binds the explicit specification claim.The canonical reward moment equations are derived from the three checked linearsystems; certificates no longer store or recheck both formulations.All moment equations, closed-class evidence and paths in result certificates arechecked by Lean's kernel. No external solver or native evaluation axiom entersthe theorem. Storm's untrusted `.additive.edges`sidecar preserves probability/reward pairs; generated `.storm.lean` certificatesare checked against the source replay. Native results use `.result.lean`.Incomplete exploration emits no new model;finite source syntax does not imply a finite normalized graph. Source andtransformed programs must each be explored separately when both are needed.The resolved input and its alignment predicate are specified in`Spec/Frontend.lean`. `sameProgram` means alignment with that resolved input;parsing and desugaring of source bytes are still outside that theorem.Native result generation reports a kernel-checkable certificate, not an independentkernel check of that certificate. Native result JSON records`certificate_status: "generated"` and `kernel_checked: false`; run Lean on the generated result file tocheck it independently. The Storm wrapper sets `kernel_checked: true` only afterthat check succeeds. Both result formats label`termination_statistics_scope: "graph"`: separate rejection and divergence probabilities describe the finitegraph/controller. The end-to-end correspondence proves the successful-output law;it does not separately identify source rejection and divergence events.