import Determinize.Proof.RewardModel.Translationnamespace Determinize.Proof.RewardModelopen Determinize.Finite Determinize.Finite.Reward Determinize.Proof.FiniteModelopen MeasureTheory Spec.RewardModelprivate def residual : State → State | .eval e env stack => .eval e env (splitStack stack).1 | .deliver v stack => .deliver v (splitStack stack).1 | .rejected => .rejectedprivate def offsets : State → List Rat | .eval _ _ stack | .deliver _ stack => (splitStack stack).2 | .rejected => []private theorem pushStack_residual_additionStack (state : State) : pushStack (residual state) (additionStack (offsets state)) = state := by cases state <;> simp [residual, offsets, pushStack, additionStack, splitStack_reconstruct]private theorem normalize_eq (state : State) : Reward.normalize state = ((offsets state).sum, pushStack (residual state) (if offsets state = [] then [] else additionStack [0])) := by cases state <;> simp [Reward.normalize, normalizeStack, residual, offsets, pushStack, additionStack, Reward.guard]/-- Extraction can only bring successful output forward in the finite horizon. -/theorem machineOutput_le_shift_normalize (state : State) (n : Nat) : machineOutput n state ≤ shift (Reward.normalize state).1 (machineOutput n (Reward.normalize state).2) := by rw [normalize_eq] simp only by_cases empty : offsets state = [] · have decomp := pushStack_residual_additionStack state simp only [empty, additionStack, List.map_nil] at decomp simp only [empty, ↓reduceIte, List.sum_nil, shift_zero, decomp] exact le_rfl · simp only [empty, ↓reduceIte] have h := addition_guard_upper (offsets state) empty n (residual state) simpa only [pushStack_residual_additionStack] using h/-- The erased context always finishes after finitely many ordinary CEK transitions. -/theorem exists_shift_normalize_le_machineOutput (state : State) (n : Nat) : ∃ horizon, shift (Reward.normalize state).1 (machineOutput n (Reward.normalize state).2) ≤ machineOutput horizon state := by refine ⟨n + (offsets state).length, ?_⟩ rw [normalize_eq] simp only by_cases empty : offsets state = [] · have decomp := pushStack_residual_additionStack state simp only [empty, additionStack, List.map_nil] at decomp simp only [empty, ↓reduceIte, List.sum_nil, shift_zero, decomp, List.length_nil, Nat.add_zero] exact le_rfl · simp only [empty, ↓reduceIte] have upper := addition_output_upper [0] n (residual state) simp only [List.sum_cons, List.sum_nil, add_zero, shift_zero] at upper exact (shift_mono _ upper).trans (by simpa only [pushStack_residual_additionStack] using addition_output_lower (offsets state) n (residual state))end Determinize.Proof.RewardModel