AFTD Auto-Formalizing Theoretical Domains

Cslib.URM.Step.from_toStandardForm

theoremverifiedformalizationimported Lean

Reverse step correspondence: if p.toStandardForm steps from s to s', then either: (1) p steps from s to s' (same step), or (2) s' is halted in p.toStandardForm, and p 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
open Cslib.URM.Program Cslib.URM.State Cslib.URM.Instr in
theorem Cslib.URM.Step.from_toStandardForm {p : Program} {s s' : State} (hstep : Step p.toStandardForm s s') :
    Step p s s' ∨
    (s'.isHalted p.toStandardForm ∧ ∃ s₂, Step p s s₂ ∧ s₂.isHalted p ∧ s'.regs = s₂.regs)
Formalizes
CSLib, `Cslib.URM.Step.from_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.
What was changed in Cslib.URM.Step.from_toStandardForm
--- Cslib/Computability/URM/StandardForm.lean:156 (Cslib.URM.Step.from_toStandardForm)
+++ as compiled here
@@ -1,7 +1,5 @@
-open Program State Instr in
-/-- Reverse step correspondence: if p.toStandardForm steps from s to s', then either:
-    (1) p steps from s to s' (same step), or
-    (2) s' is halted in p.toStandardForm, and p steps to a state that is also halted
-        with the same registers (this only happens for jumps with unbounded targets). -/
-theorem Step.from_toStandardForm {p : Program} {s s' : State} (hstep : Step p.toStandardForm s s') :
+set_option autoImplicit true in
+set_option relaxedAutoImplicit true in
+open Cslib.URM.Program Cslib.URM.State Cslib.URM.Instr in
+theorem Cslib.URM.Step.from_toStandardForm {p : Program} {s s' : State} (hstep : Step p.toStandardForm s s') :
     Step p s s' ∨
Verified
08 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 24
Used by 1
  • urm_halts_toStandardFormFor any URM program p and input list inputs, p halts on inputs if and only if its standard form p.toStandardForm halts on inputs.

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true inopen Cslib.URM.Program Cslib.URM.State Cslib.URM.Instr in/-- Reverse step correspondence: if p.toStandardForm steps from s to s', then either: (1) p steps from s to s' (same step), or (2) s' is halted in p.toStandardForm, and p steps to a state that is also halted with the same registers (this only happens for jumps with unbounded targets). -/theorem Cslib.URM.Step.from_toStandardForm {p : Program} {s s' : State} (hstep : Step p.toStandardForm s s') :    Step p s s' ∨    (s'.isHalted p.toStandardForm ∧ ∃ s₂, Step p s s₂ ∧ s₂.isHalted p ∧ s'.regs = s₂.regs) := by  cases hstep with  | jump_eq hinstr _ =>    simp only [Program.getElem?_toStandardForm, Option.map_eq_some_iff] at hinstr    obtain ⟨instr, _⟩ := hinstr    cases instr with    | J => grind [=> jump_eq]    | _ => grind  | _ => grind [getElem?_toStandardForm, Option.map_eq_some_iff]
See it in the graphDiscuss this resultChallenge it