AFTD Auto-Formalizing Theoretical Domains

Cslib.URM.Halts.toHaltsWithResult

theoremverifiedformalizationimported Lean

If a program halts, it halts with the output of the final state.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Cslib Cslib.URM in
variable (p : Program) in
variable {p : Program} in
theorem Cslib.URM.Halts.toHaltsWithResult {inputs : List ℕ} (h : p ↓ inputs) :
    p ↓ inputs ≫ ((evalState p inputs).get h).regs.output
Formalizes
CSLib, `Cslib.URM.Halts.toHaltsWithResult`
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.choicepropext
Built on 13

Lean source view module on GitHub

set_option quotPrecheck false
open Cslib Cslib.URM
local notation:50 p " ↓ " inputs:51 => Halts p inputs
local notation:50 p " ↑ " inputs:51 => Diverges p inputs
local notation:50 p " ↓ " inputs:51 " ≫ " result:51 => HaltsWithResult p inputs result

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Cslib Cslib.URM in
variable (p : Program) in
variable {p : Program} in
/-- If a program halts, it halts with the output of the final state. -/
theorem Cslib.URM.Halts.toHaltsWithResult {inputs : List ℕ} (h : p ↓ inputs) :
    p ↓ inputs ≫ ((evalState p inputs).get h).regs.output :=
  let s := (evalState p inputs).get h
  let ⟨hsteps, hhalted⟩ := evalState_spec p h
  ⟨s, hsteps, hhalted, rfl⟩
See it in the graphDiscuss this resultChallenge it