AFTD Auto-Formalizing Theoretical Domains

Cslib.URM.Step.toStandardForm

theoremverifiedformalizationimported Lean

Forward step correspondence: if p steps from s to s', then either: (1) p.toStandardForm steps from s to s' (same step), or (2) s' is halted in p, and p.toStandardForm steps to a state that is also halted with the same registers (this only happens for jumps with unbounded targets).

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
theorem Cslib.URM.Step.toStandardForm {p : Program} {s s' : State} (hstep : Step p s s') :
    Step p.toStandardForm s s' ∨
    (s'.isHalted p ∧ ∃ s₂, Step p.toStandardForm s s₂ ∧
      s₂.isHalted p.toStandardForm ∧ s'.regs = s₂.regs)
Formalizes
CSLib, `Cslib.URM.Step.toStandardForm`
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 33
Used by 2

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true in/-- Forward step correspondence: if p steps from s to s', then either: (1) p.toStandardForm steps from s to s' (same step), or (2) s' is halted in p, and p.toStandardForm steps to a state that is also halted with the same registers (this only happens for jumps with unbounded targets). -/theorem Cslib.URM.Step.toStandardForm {p : Program} {s s' : State} (hstep : Step p s s') :    Step p.toStandardForm s s' ∨    (s'.isHalted p ∧ ∃ s₂, Step p.toStandardForm s s₂ ∧      s₂.isHalted p.toStandardForm ∧ s'.regs = s₂.regs) := by  cases hstep with  | zero hinstr =>    left    exact Step.zero (by simp [Program.getElem?_toStandardForm, hinstr])  | succ hinstr =>    left    exact Step.succ (by simp [Program.getElem?_toStandardForm, hinstr])  | transfer hinstr =>    left    exact Step.transfer (by simp [Program.getElem?_toStandardForm, hinstr])  | @jump_ne m n q hinstr hne =>    left    have hcap : p.toStandardForm[s.pc]? = some (Instr.J m n (min q p.length)) := by      simp [Program.getElem?_toStandardForm, hinstr]    exact Step.jump_ne hcap hne  | @jump_eq m n q hinstr heq =>    have (x : ℕ) (h : min q p.length = x) : p.toStandardForm[s.pc]? = some (Instr.J m n x) := by      grind [Program.getElem?_toStandardForm, Instr.capJump]    by_cases q ≤ p.length    · grind [Step.jump_eq]    · right      split_ands      · grind [State.isHalted]      · use ⟨p.length, s.regs⟩        grind [State.isHalted, Program.toStandardForm_length]
See it in the graphDiscuss this resultChallenge it