import Determinize.Spec.Semanticsimport Mathlib.Algebra.BigOperators.Ring.Finset/-!# Finite modelsA finite Markov chain with rational transition probabilities. Evaluation stops at a state thatreturns a rational reward or rejects. The output law of the chain is defined here, and`Model.Matches` relates it to the output law of a program.-/namespace Determinize.Spec.FiniteModelopen MeasureTheory/-- What happens at a state: evaluation continues from a `transient` state, stops with a rewardat a `returned` state, and stops without output at a `rejected` state. -/inductive StateKind where | transient | returned (reward : Rat) | rejectedderiving DecidableEq, Repr/-- Evaluation stops at terminal states and rewards are paid once, on return.Transition rows at terminal states are ignored by the output semantics. -/structure Model where /-- The number of states. -/ size : Nat /-- The state in which evaluation starts. -/ initial : Fin size /-- Whether each state is transient, returns a reward, or rejects. -/ kind : Fin size → StateKind /-- The probability of moving from the first state to the second in one step. -/ transition : Fin size → Fin size → Rat nonnegative : ∀ i j, 0 ≤ transition i j normalized : ∀ i, ∑ j, transition i j = 1/-- Probability that evaluation is still transient after at most `steps` transitions. -/def Model.survivalWithin (model : Model) : Nat → Fin model.size → Rat | 0, state => if model.kind state = .transient then 1 else 0 | steps + 1, state => if model.kind state = .transient then ∑ next, model.transition state next * model.survivalWithin steps next else 0/-- Unnormalized real output accumulated within `steps` transitions. -/noncomputable def Model.outputWithin (model : Model) : Nat → Fin model.size → Measure ℝ | 0, state => match model.kind state with | .returned reward => Measure.dirac (reward : ℝ) | _ => 0 | steps + 1, state => match model.kind state with | .returned reward => Measure.dirac (reward : ℝ) | .rejected => 0 | .transient => ∑ next, ENNReal.ofReal (model.transition state next : ℝ) • model.outputWithin steps next/-- Rejection and nontermination contribute no output mass. There is no conditioning. -/noncomputable def Model.outputMeasure (model : Model) : Measure ℝ := ⨆ steps, model.outputWithin steps model.initial/-- The model represents the entire output law of this exact core program, andaccepted programs cannot get stuck. Rejection and divergence remain possible. -/def Model.Matches (model : Model) (program : Paper.Expr) : Prop := Paper.DomainSafe program ∧ model.outputMeasure = Paper.bigStepMeasure programend Determinize.Spec.FiniteModel