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.Cslib.URM.isHalted_iff_normal← Cslib.URM.isHalted_iff_normal (Cslib/Computability/URM/Execution.lean:113): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 13
- Cslib.URM.State.instDecidableIsHaltedCslib.URM.State.instDecidableIsHalted
- Cslib.URM.InstrURM instructions. -
Z n: Set register n to zero -S n: Increment register n by one -T m n: Transfer (copy) the contents of register… - Cslib.URM.Step.no_step_of_haltedA halted state has no successor in the step relation.
- Cslib.URM.Regs.writeWrite value v to register n.
- Cslib.URM.State.isHaltedA state is halted if the program counter is at or beyond the program length.
- Relation.ReducibleAn element is reducible with respect to a relation if there is a value it is related to.
- Relation.NormalAn element is normal if it is not reducible.
- Cslib.URM.State.instInhabitedCslib.URM.State.instInhabited
- Cslib.URM.Regs.readRead the contents of register n.
- Cslib.URM.State.instReprCslib.URM.State.instRepr
- Cslib.URM.StepSingle-step execution relation for URMs. Each constructor corresponds to one of the four instruction types: -
zero: ExecuteZ n(set… - Cslib.URM.StateMachine state: program counter (0-indexed) and register contents.
- Cslib.URM.ProgramA URM program is a list of instructions.
- Used by 1
- Cslib.URM.halts_iff_normalizableHalting is equivalent to normalizability in the reduction system.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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⟩