AFTD Auto-Formalizing Theoretical Domains

Cslib.URM.straight_line_halts_from_regs

theoremverifiedformalizationimported Lean

Straight-line programs halt from any starting registers, not just State.init. Useful for chaining: after running one program, we can run the next straight-line segment from whatever registers we're in.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
theorem Cslib.URM.straight_line_halts_from_regs {p : Program} (hsl : p.IsStraightLine) (r : Regs) :
    ∃ s, Steps p ⟨0, r⟩ s ∧ s.isHalted p ∧ s.pc = p.length
Formalizes
CSLib, `Cslib.URM.straight_line_halts_from_regs`
Lean proof
By Jesse Alama, from github.com/leanprover/cslib at 3951377e5a3f (Copyright (c) 2026 Jesse Alama. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.33.0.
Verified
08 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 22
Used by 3

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true in/-- Straight-line programs halt from any starting registers, not just State.init. Useful for chaining: after running one program, we can run the next straight-line segment from whatever registers we're in. -/theorem Cslib.URM.straight_line_halts_from_regs {p : Program} (hsl : p.IsStraightLine) (r : Regs) :    ∃ s, Steps p ⟨0, r⟩ s ∧ s.isHalted p ∧ s.pc = p.length := by  suffices h : ∀ s : State, s.pc ≤ p.length → ∃ s', Steps p s s' ∧ s'.pc = p.length by    obtain ⟨s', hsteps, hpc'⟩ := h ⟨0, r⟩ (Nat.zero_le _)    exact ⟨s', hsteps, Nat.le_of_eq hpc'.symm, hpc'⟩  intro s hpc_le  generalize hrem : p.length - s.pc = remaining  induction remaining using Nat.strong_induction_on generalizing s with  | h n ih =>  by_cases hhalted : s.pc ≥ p.length  · grind  · have jmp : ¬p[s.pc].IsJump := by apply hsl; grind    have := Step.of_nonJump (by lia) jmp    grind [Relation.ReflTransGen.head]
See it in the graphDiscuss this resultChallenge it