AFTD Auto-Formalizing Theoretical Domains

Cslib.URM.isHalted_iff_normal

theoremverifiedformalizationimported Lean

A state is halted iff it is normal (has no successor) in the reduction system.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
variable (p : Program) in
theorem Cslib.URM.isHalted_iff_normal {p : Program} {s : State} :
    s.isHalted p ↔ Relation.Normal (Step p) s
Formalizes
CSLib, `Cslib.URM.isHalted_iff_normal`
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 13
Used by 1

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true invariable (p : Program) in/-- A state is halted iff it is normal (has no successor) in the reduction system. -/theorem Cslib.URM.isHalted_iff_normal {p : Program} {s : State} :    s.isHalted p ↔ Relation.Normal (Step p) s := by  constructor  · intro hhalted ⟨s', hstep⟩    exact Step.no_step_of_halted hhalted hstep  · intro hnormal    -- If not halted, then p[s.pc]? = some instr for some instruction    by_contra hnothalted    simp only [State.isHalted, not_le] at hnothalted    have hlt : s.pc < p.length := hnothalted    have hinstr : p[s.pc]? = some p[s.pc] := List.getElem?_eq_getElem hlt    -- Any instruction can step, contradicting hnormal    cases hp : p[s.pc] with    | Z n => exact hnormal ⟨_, Step.zero (hp ▸ hinstr)⟩    | S n => exact hnormal ⟨_, Step.succ (hp ▸ hinstr)⟩    | T m n => exact hnormal ⟨_, Step.transfer (hp ▸ hinstr)⟩    | J m n q =>      by_cases heq : s.regs.read m = s.regs.read n      · exact hnormal ⟨_, Step.jump_eq (hp ▸ hinstr) heq⟩      · exact hnormal ⟨_, Step.jump_ne (hp ▸ hinstr) heq⟩
See it in the graphDiscuss this resultChallenge it