AFTD Auto-Formalizing Theoretical Domains

Cslib.URM.halts_iff_normalizable

theoremverifiedformalizationimported Lean

Halting is equivalent to normalizability in the reduction system.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
variable (p : Program) in
theorem Cslib.URM.halts_iff_normalizable {p : Program} {inputs : List ℕ} :
    Halts p inputs ↔ Relation.Normalizable (Step p) (State.init inputs)
Formalizes
CSLib, `Cslib.URM.halts_iff_normalizable`
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 10

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true invariable (p : Program) in/-- Halting is equivalent to normalizability in the reduction system. -/theorem Cslib.URM.halts_iff_normalizable {p : Program} {inputs : List ℕ} :    Halts p inputs ↔ Relation.Normalizable (Step p) (State.init inputs) := by  grind [Halts, isHalted_iff_normal]
See it in the graphDiscuss this resultChallenge it