import Determinize.Proof.FiniteModel.Progressimport Determinize.Proof.FiniteModel.MeasureLawsnamespace Determinize.Proof.FiniteModelopen Spec.Paper Determinize.Finite MeasureTheorynoncomputable def machineOutput : Nat → State → Measure ℝ | 0, state => match step state with | .ok (.returned reward) => Measure.dirac (reward : ℝ) | _ => 0 | fuel + 1, state => match step state with | .ok (.returned reward) => Measure.dirac (reward : ℝ) | .ok (.next _ successors) => weightedOutput successors (machineOutput fuel) | _ => 0noncomputable def machineOutputMeasure (state : State) : Measure ℝ := ⨆ fuel, machineOutput fuel statedef SameObservations (before after : State) : Prop := (∀ fuel, Cumulative.outputMeasure fuel (stateExpr before) = Cumulative.outputMeasure fuel (stateExpr after)) ∧ (∀ fuel, DomainSafeAt fuel (stateExpr before) ↔ DomainSafeAt fuel (stateExpr after))def PaperStep (before : State) (successors : List (Rat × State)) : Prop := Cumulative.outputMeasure 0 (stateExpr before) = 0 ∧ (∀ fuel, Cumulative.outputMeasure (fuel + 1) (stateExpr before) = weightedOutput successors (fun after ↦ Cumulative.outputMeasure fuel (stateExpr after))) ∧ (∀ fuel, DomainSafeAt (fuel + 1) (stateExpr before) ↔ ∀ outcome ∈ successors, 0 < outcome.1 → DomainSafeAt fuel (stateExpr outcome.2))def StepMeaning (state : State) : Step → Prop | .returned reward => (∀ fuel, Cumulative.outputMeasure fuel (stateExpr state) = Measure.dirac (reward : ℝ)) ∧ DomainSafe (stateExpr state) | .rejected => (∀ fuel, Cumulative.outputMeasure fuel (stateExpr state) = 0) ∧ DomainSafe (stateExpr state) | .next _ successors => (∃ after, successors = [(1, after)] ∧ Bookkeeping state ∧ SameObservations state after) ∨ PaperStep state successorstheorem machineOutput_mono (state : State) : Monotone (fun fuel ↦ machineOutput fuel state) := by apply monotone_nat_of_le_succ intro fuel induction fuel generalizing state with | zero => cases h : step state <;> simp only [machineOutput, h, Std.le_refl] rename_i result cases result <;> simp only [Std.le_refl] exact bot_le | succ fuel ih => cases h : step state with | error failure => simp [machineOutput, h] | ok result => cases result <;> simp only [machineOutput, h] · exact weightedOutput_mono _ _ _ (fun entry _ _ ↦ ih entry.2) all_goals exact le_rfltheorem machineOutput_le_paper (initial : State) (meaning : ∀ state, MachineReachable initial state → ∀ result, step state = .ok result → StepMeaning state result) (fuel : Nat) (state : State) (reachable : MachineReachable initial state) : machineOutput fuel state ≤ Cumulative.outputMeasure fuel (stateExpr state) := by induction fuel generalizing state with | zero => cases action : step state with | error failure => simpa only [machineOutput, action] using (Measure.zero_le _) | ok result => have localMeaning := meaning state reachable result action cases result with | returned reward => simpa [machineOutput, action] using (localMeaning.1 0).ge | rejected => simpa only [machineOutput, action] using (Measure.zero_le _) | next evidence successors => simpa only [machineOutput, action] using (Measure.zero_le _) | succ fuel ih => cases action : step state with | error failure => simpa only [machineOutput, action] using (Measure.zero_le _) | ok result => have localMeaning := meaning state reachable result action cases result with | returned reward => simpa [machineOutput, action] using (localMeaning.1 (fuel + 1)).ge | rejected => simpa only [machineOutput, action] using (Measure.zero_le _) | next evidence successors => rcases localMeaning with ⟨after, rfl, _, same⟩ | advance · have nextReach : MachineReachable initial after := MachineReachable.next reachable action (by simp) (by norm_num : (0 : Rat) < 1) have bound := ih after nextReach rw [← same.1 fuel] at bound simpa [machineOutput, action, weightedOutput] using bound.trans (Proof.Paper.direct_cumulative_mono _ (Nat.le_succ fuel)) · rw [machineOutput, action, advance.2.1 fuel] exact weightedOutput_mono _ _ _ (fun entry member positive ↦ ih entry.2 (.next reachable action member positive))theorem execution_safe (initial : State) (meaning : ∀ state, MachineReachable initial state → ∀ result, step state = .ok result → StepMeaning state result) (noFailure : ∀ state, MachineReachable initial state → ∀ failure, step state ≠ .error failure) (fuel : Nat) (state : State) (reachable : MachineReachable initial state) : DomainSafeAt fuel (stateExpr state) := by cases fuel with | zero => trivial | succ fuel => cases action : step state with | error failure => exact False.elim (noFailure state reachable failure action) | ok result => have localMeaning := meaning state reachable result action cases result with | returned reward => exact localMeaning.2 (fuel + 1) | rejected => exact localMeaning.2 (fuel + 1) | next evidence successors => rcases localMeaning with ⟨after, rfl, bookkeeping, same⟩ | advance · have nextReach : MachineReachable initial after := MachineReachable.next reachable action (by simp) (by norm_num : (0 : Rat) < 1) have decrease := bookkeepingRank_lt state bookkeeping _ _ action 1 after (by simp) exact (same.2 (fuel + 1)).mpr (execution_safe initial meaning noFailure (fuel + 1) after nextReach) · apply (advance.2.2 fuel).mpr intro entry member positive exact execution_safe initial meaning noFailure fuel entry.2 (.next reachable action member positive)termination_by (fuel, bookkeepingRank state)decreasing_by all_goals omegatheorem paper_le_machine_horizon (initial : State) (meaning : ∀ state, MachineReachable initial state → ∀ result, step state = .ok result → StepMeaning state result) (noFailure : ∀ state, MachineReachable initial state → ∀ failure, step state ≠ .error failure) (fuel : Nat) (state : State) (reachable : MachineReachable initial state) : ∃ horizon, Cumulative.outputMeasure fuel (stateExpr state) ≤ machineOutput horizon state := by cases action : step state with | error failure => exact False.elim (noFailure state reachable failure action) | ok result => have localMeaning := meaning state reachable result action cases result with | returned reward => exact ⟨0, by simp [machineOutput, action, localMeaning.1 fuel]⟩ | rejected => exact ⟨0, by simp [machineOutput, action, localMeaning.1 fuel]⟩ | next evidence successors => rcases localMeaning with ⟨after, rfl, bookkeeping, same⟩ | advance · have nextReach : MachineReachable initial after := MachineReachable.next reachable action (by simp) (by norm_num : (0 : Rat) < 1) have decrease := bookkeepingRank_lt state bookkeeping _ _ action 1 after (by simp) obtain ⟨horizon, bound⟩ := paper_le_machine_horizon initial meaning noFailure fuel after nextReach refine ⟨horizon + 1, ?_⟩ simpa [machineOutput, action, weightedOutput, same.1 fuel] using bound · cases fuel with | zero => exact ⟨0, by rw [advance.1]; exact bot_le⟩ | succ fuel => have bounds : ∀ entry ∈ successors, 0 < entry.1 → ∃ horizon, Cumulative.outputMeasure fuel (stateExpr entry.2) ≤ machineOutput horizon entry.2 := by intro entry member positive exact paper_le_machine_horizon initial meaning noFailure fuel entry.2 (.next reachable action member positive) obtain ⟨horizon, bound⟩ := weightedOutput_uniform_bound successors (fun after ↦ Cumulative.outputMeasure fuel (stateExpr after)) machineOutput machineOutput_mono bounds exact ⟨horizon + 1, by simpa [machineOutput, action, advance.2.1 fuel] using bound⟩termination_by (fuel, bookkeepingRank state)decreasing_by all_goals omegatheorem execution_output_eq (initial : State) (meaning : ∀ state, MachineReachable initial state → ∀ result, step state = .ok result → StepMeaning state result) (noFailure : ∀ state, MachineReachable initial state → ∀ failure, step state ≠ .error failure) (state : State) (reachable : MachineReachable initial state) : machineOutputMeasure state = bigStepMeasure (stateExpr state) := by rw [Proof.Paper.bigStepMeasure_eq_iSup_cumulative] unfold machineOutputMeasure apply le_antisymm · apply iSup_le intro fuel exact (machineOutput_le_paper initial meaning fuel state reachable).trans (le_iSup (fun n ↦ Cumulative.outputMeasure n (stateExpr state)) fuel) · apply iSup_le intro fuel obtain ⟨horizon, bound⟩ := paper_le_machine_horizon initial meaning noFailure fuel state reachable exact bound.trans (le_iSup (fun n ↦ machineOutput n state) horizon)end Determinize.Proof.FiniteModel