import Determinize.Finite.Graphimport Determinize.Proof.FiniteModel.Equalityimport Determinize.Proof.FiniteModel.Substitution/-!Internal graph invariants for the executable machine. These are intermediateproof obligations; they do not establish the paper's `Model.Matches` contract.-/namespace Determinize.Finiteopen Spec.Paper Spec.FiniteModel Checkingdef Candidate.state (candidate : Candidate) (i : Fin candidate.states.size) : State := candidate.states[i]def Candidate.row (candidate : Candidate) (i : Fin candidate.states.size) : Row := candidate.rows[i.val]?.getD ⟨.rejected, #[]⟩def Candidate.weight (candidate : Candidate) (i j : Fin candidate.states.size) : Rat := ((candidate.row i).edges.toList.map fun edge ↦ if edge.target = j.val then edge.probability else 0).sum/-- Local replay checks the entire probability law, including successors withpositive mass that are absent from the supplied graph. -/def Candidate.RowReplays (candidate : Candidate) (i : Fin candidate.states.size) : Prop := match step (candidate.state i) with | .error _ => False | .ok (.returned reward) => (candidate.row i).kind = .returned reward | .ok .rejected => (candidate.row i).kind = .rejected | .ok (.next _ successors) => (candidate.row i).kind = .transient ∧ (∀ outcome ∈ successors, 0 ≤ outcome.1) ∧ (∀ outcome ∈ successors, 0 < outcome.1 → ∃ j : Fin candidate.states.size, candidate.state j = outcome.2) ∧ (∀ j : Fin candidate.states.size, candidate.weight i j = (successors.map fun outcome ↦ if outcome.2 = candidate.state j then outcome.1 else 0).sum)instance (candidate : Candidate) (i : Fin candidate.states.size) : Decidable (candidate.RowReplays i) := by unfold Candidate.RowReplays split · infer_instance · infer_instance · infer_instance · infer_instancestructure Candidate.MatrixValid (candidate : Candidate) : Prop where nonnegative : ∀ i j, 0 ≤ candidate.weight i j normalized : ∀ i, ∑ j, candidate.weight i j = 1 absorbing : ∀ i, (candidate.row i).kind ≠ .transient → ∀ j, candidate.weight i j = if i = j then 1 else 0instance (candidate : Candidate) : Decidable candidate.MatrixValid := decidable_of_iff ((∀ i j, 0 ≤ candidate.weight i j) ∧ (∀ i, ∑ j, candidate.weight i j = 1) ∧ (∀ i, (candidate.row i).kind ≠ .transient → ∀ j, candidate.weight i j = if i = j then 1 else 0)) ⟨fun ⟨a, b, c⟩ ↦ ⟨a, b, c⟩, fun ⟨a, b, c⟩ ↦ ⟨a, b, c⟩⟩/-- Sparse representation checks additionally reject out-of-range, duplicate,and nonpositive edges, even when they cancel in the induced matrix. -/def Candidate.EdgesValid (candidate : Candidate) (i : Fin candidate.states.size) : Prop := ((candidate.row i).edges.toList.map Edge.target).Nodup ∧ ∀ edge ∈ (candidate.row i).edges.toList, edge.target < candidate.states.size ∧ 0 < edge.probabilityinstance (candidate : Candidate) (i : Fin candidate.states.size) : Decidable (candidate.EdgesValid i) := inferInstanceAs (Decidable (_ ∧ _))def initialState (source : Core) (subject : Subject) : State := .eval (match subject with | .source => source | .determinized => source.determinize) [] []structure Candidate.Aligned (candidate : Candidate) (source : Core) (subject : Subject) : Prop where initial : candidate.states[candidate.initial]? = some (initialState source subject) source_scoped : Determinize.Proof.FiniteModel.Binding.Scoped 0 source injective : Function.Injective candidate.stateinstance (candidate : Candidate) (source : Core) (subject : Subject) : Decidable (candidate.Aligned source subject) := decidable_of_iff (candidate.states[candidate.initial]? = some (initialState source subject) ∧ Determinize.Proof.FiniteModel.Binding.Scoped 0 source ∧ Function.Injective candidate.state) ⟨fun ⟨a, b, c⟩ ↦ ⟨a, b, c⟩, fun ⟨a, b, c⟩ ↦ ⟨a, b, c⟩⟩structure Candidate.ReplayValid (candidate : Candidate) (source : Core) (subject : Subject) : Prop where rows_size : candidate.rows.size = candidate.states.size initial_lt : candidate.initial < candidate.states.size aligned : candidate.Aligned source subject matrix : candidate.MatrixValid edges : ∀ i, candidate.EdgesValid i replays : ∀ i, candidate.RowReplays iinstance (candidate : Candidate) (source : Core) (subject : Subject) : Decidable (candidate.ReplayValid source subject) := decidable_of_iff (candidate.rows.size = candidate.states.size ∧ candidate.initial < candidate.states.size ∧ candidate.Aligned source subject ∧ candidate.MatrixValid ∧ (∀ i, candidate.EdgesValid i) ∧ (∀ i, candidate.RowReplays i)) ⟨fun ⟨a, b, c, d, e, f⟩ ↦ ⟨a, b, c, d, e, f⟩, fun ⟨a, b, c, d, e, f⟩ ↦ ⟨a, b, c, d, e, f⟩⟩/-- Structural evidence shared by replay formats; state labels need not be distinct. -/structure Candidate.GraphValid (candidate : Candidate) : Prop where initial_lt : candidate.initial < candidate.states.size matrix : candidate.MatrixValid edges : ∀ i, candidate.EdgesValid iabbrev Candidate.graphModel (candidate : Candidate) (valid : candidate.GraphValid) : Model where size := candidate.states.size initial := ⟨candidate.initial, valid.initial_lt⟩ kind := fun i ↦ (candidate.row i).kind transition := candidate.weight nonnegative := valid.matrix.nonnegative normalized := valid.matrix.normalized/-- This constructs a finite rational model, but supplies no `Matches` proof. -/abbrev Candidate.toModel (candidate : Candidate) {source : Core} {subject : Subject} (valid : candidate.ReplayValid source subject) : Model where size := candidate.states.size initial := ⟨candidate.initial, valid.initial_lt⟩ kind := fun i ↦ (candidate.row i).kind transition := candidate.weight nonnegative := valid.matrix.nonnegative normalized := valid.matrix.normalizedtheorem replay_successor_covered (candidate : Candidate) {source : Core} {subject : Subject} (valid : candidate.ReplayValid source subject) (i : Fin candidate.states.size) (evidence : Evidence) (successors : List (Rat × State)) (action : step (candidate.state i) = .ok (.next evidence successors)) (outcome : Rat × State) (member : outcome ∈ successors) (positive : 0 < outcome.1) : ∃ j : Fin candidate.states.size, candidate.state j = outcome.2 := by have localValid := valid.replays i simp only [Candidate.RowReplays, action] at localValid exact localValid.2.2.1 outcome member positivetheorem replay_transition_weight (candidate : Candidate) {source : Core} {subject : Subject} (valid : candidate.ReplayValid source subject) (i j : Fin candidate.states.size) (evidence : Evidence) (successors : List (Rat × State)) (action : step (candidate.state i) = .ok (.next evidence successors)) : (candidate.toModel valid).transition i j = (successors.map fun outcome ↦ if outcome.2 = candidate.state j then outcome.1 else 0).sum := by have localValid := valid.replays i simp only [Candidate.RowReplays, action] at localValid exact localValid.2.2.2 j/-- Reachability along positive-probability transitions of the executable machine. -/inductive MachineReachable (initial : State) : State → Prop where | initial : MachineReachable initial initial | next {before after : State} {probability : Rat} {evidence : Evidence} {successors : List (Rat × State)} : MachineReachable initial before → step before = .ok (.next evidence successors) → (probability, after) ∈ successors → 0 < probability → MachineReachable initial aftertheorem replay_initial (candidate : Candidate) {source : Core} {subject : Subject} (valid : candidate.ReplayValid source subject) : candidate.state (candidate.toModel valid).initial = initialState source subject := by have aligned := valid.aligned.initial simpa [valid.initial_lt, Candidate.state, Candidate.toModel] using aligned/-- Coverage holds for paths of arbitrary length, not just the explorer's horizon. -/theorem replay_reachable_covered (candidate : Candidate) {source : Core} {subject : Subject} (valid : candidate.ReplayValid source subject) {state : State} (reachable : MachineReachable (initialState source subject) state) : ∃ i : Fin candidate.states.size, candidate.state i = state := by induction reachable with | initial => exact ⟨(candidate.toModel valid).initial, replay_initial candidate valid⟩ | next previous action member positive ih => obtain ⟨i, hi⟩ := ih exact replay_successor_covered candidate valid i _ _ (hi ▸ action) _ member positivetheorem replay_no_failure (candidate : Candidate) {source : Core} {subject : Subject} (valid : candidate.ReplayValid source subject) (i : Fin candidate.states.size) (failure : Failure) : step (candidate.state i) ≠ .error failure := by intro action have localValid := valid.replays i simp [Candidate.RowReplays, action] at localValidtheorem replay_reachable_no_failure (candidate : Candidate) {source : Core} {subject : Subject} (valid : candidate.ReplayValid source subject) {state : State} (reachable : MachineReachable (initialState source subject) state) (failure : Failure) : step state ≠ .error failure := by obtain ⟨i, hi⟩ := replay_reachable_covered candidate valid reachable rw [← hi] exact replay_no_failure candidate valid i failureend Determinize.Finite