Source lean/Determinize/Proof/FiniteModel/Graph.lean
import Determinize.Proof.FiniteModel.Executionimport Determinize.Proof.FiniteModel.Modelnamespace Determinize.Proof.FiniteModelopen Spec.Paper Spec.FiniteModel Determinize.Finite MeasureTheorydef successorWeight {α : Type} [DecidableEq α] (outcomes : List (Rat × α)) (state : α) : Rat :=  (outcomes.map fun entry ↦ if entry.2 = state then entry.1 else 0).sumtheorem successorWeight_nonnegative {α : Type} [DecidableEq α] (outcomes : List (Rat × α))    (nonnegative : ∀ entry ∈ outcomes, 0 ≤ entry.1) (state : α) :    0 ≤ successorWeight outcomes state := by  apply List.sum_nonneg  intro p member  obtain ⟨entry, entryMember, rfl⟩ := List.mem_map.mp member  split_ifs  · exact nonnegative entry entryMember  · rfltheorem weightedOutput_group {α : Type} [DecidableEq α] {n : Nat}    (states : Fin n → α) (unique : Function.Injective states)    (outcomes : List (Rat × α)) (nonnegative : ∀ entry ∈ outcomes, 0 ≤ entry.1)    (covered : ∀ entry ∈ outcomes, 0 < entry.1 → ∃ i, states i = entry.2)    (output : α → Measure ℝ) :    weightedOutput outcomes output =      ∑ i, ENNReal.ofReal (successorWeight outcomes (states i) : ℝ) • output (states i) := by  induction outcomes with  | nil => simp [weightedOutput, successorWeight]  | cons entry rest ih =>    have restNonnegative : ∀ e ∈ rest, 0 ≤ e.1 := fun e he ↦ nonnegative e (by simp [he])    have restCovered : ∀ e ∈ rest, 0 < e.1 → ∃ i, states i = e.2 :=      fun e he ↦ covered e (by simp [he])    have splitWeight (i : Fin n) :        ENNReal.ofReal (successorWeight (entry :: rest) (states i) : ℝ) =          (if entry.2 = states i then ENNReal.ofReal (entry.1 : ℝ) else 0) +            ENNReal.ofReal (successorWeight rest (states i) : ℝ) := by      simp only [successorWeight, List.map_cons, List.sum_cons, Rat.cast_add]      rw [ENNReal.ofReal_add]      · split_ifs <;> simp      · split_ifs        · exact_mod_cast nonnegative entry (by simp)        · simp      · exact_mod_cast successorWeight_nonnegative rest restNonnegative (states i)    simp only [weightedOutput, List.map_cons, List.sum_cons, splitWeight, add_smul,      Finset.sum_add_distrib]    congr 1    · by_cases positive : 0 < entry.1      · obtain ⟨i, hi⟩ := covered entry (by simp) positive        have indices (j : Fin n) : entry.2 = states j ↔ j = i := by          rw [← hi]          exact ⟨fun eq ↦ (unique eq).symm, fun eq ↦ eq ▸ rfl⟩        simp [indices, hi]      · have zero : ENNReal.ofReal (entry.1 : ℝ) = 0 :=          ENNReal.ofReal_eq_zero.mpr (by exact_mod_cast le_of_not_gt positive)        simp [zero]    · exact ih restNonnegative restCoveredtheorem replay_machineOutput (candidate : Candidate) {source : Spec.Paper.Core} {subject : Subject}    (valid : candidate.ReplayValid source subject) (fuel : Nat) (i : Fin candidate.states.size) :    (candidate.toModel valid).outputWithin fuel i = machineOutput fuel (candidate.state i) := by  induction fuel generalizing i with  | zero =>    have row := valid.replays i    cases action : step (candidate.state i) with    | error failure => simp [Candidate.RowReplays, action] at row    | ok result =>      cases result <;> simp only [Candidate.RowReplays, action] at row      all_goals simp_all [Model.outputWithin, machineOutput]  | succ fuel ih =>    have row := valid.replays i    cases action : step (candidate.state i) with    | error failure => simp [Candidate.RowReplays, action] at row    | ok result =>      cases result with      | returned reward =>        simp only [Candidate.RowReplays, action] at row        simp [Model.outputWithin, row, machineOutput, action]      | rejected =>        simp only [Candidate.RowReplays, action] at row        simp [Model.outputWithin, row, machineOutput, action]      | next evidence successors =>        simp only [Candidate.RowReplays, action] at row        rw [Model.outputWithin.eq_2 (candidate.toModel valid) i fuel]        have kind : (candidate.toModel valid).kind i = .transient := row.1        rw [kind]        change (∑ j : Fin candidate.states.size,          ENNReal.ofReal (candidate.weight i j : ℝ) •            (candidate.toModel valid).outputWithin fuel j) = _        simp only [machineOutput, action]        simp_rw [ih, row.2.2.2]        exact (weightedOutput_group candidate.state valid.aligned.injective successors          row.2.1 row.2.2.1 (machineOutput fuel)).symmtheorem replay_machineOutputMeasure (candidate : Candidate) {source : Spec.Paper.Core}    {subject : Subject}    (valid : candidate.ReplayValid source subject) :    (candidate.toModel valid).outputMeasure =        machineOutputMeasure (initialState source subject) := by  unfold Model.outputMeasure machineOutputMeasure  apply iSup_congr  intro fuel  simpa only [replay_initial candidate valid] using    replay_machineOutput candidate valid fuel (candidate.toModel valid).initialend Determinize.Proof.FiniteModel