AFTD Auto-Formalizing Theoretical Domains

urm_halts_toStandardForm

theoremverifiedoriginal

For any URM program p and input list inputs, p halts on inputs if and only if its standard form p.toStandardForm halts on inputs.

Statement

open Cslib.URM in
theorem urm_halts_toStandardForm (p : Program) (inputs : List ℕ) :
    Halts p.toStandardForm inputs ↔ Halts p inputs
Related work
Cutland, Computability: An Introduction to Recursive Function Theory
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 15
  • Cslib.URM.HaltsA program halts on given inputs if execution reaches a halted state. This is equivalent to (Step p).Normalizable (State.init inputs) —…
  • Cslib.URM.Program.toStandardFormConvert a program to standard form by capping all jump targets at the program length.
  • urm_halts_toStandardForm_of_haltsIf a URM program p halts on inputs, then its standard form p.toStandardForm halts on inputs.
  • Cslib.URM.RegsRegister contents: maps register indices to natural number contents. Uses the functional representation ℕ → ℕ for efficiency with…
  • Cslib.URM.StepSingle-step execution relation for URMs. Each constructor corresponds to one of the four instruction types: - zero: Execute Z n (set…
  • Cslib.URM.Program.toStandardForm_lengthtoStandardForm preserves program length.
  • Cslib.URM.State.isHalted_iffCslib.URM.State.isHalted_iff
  • Cslib.URM.StateMachine state: program counter (0-indexed) and register contents.
  • Cslib.URM.State.initInitial state for a program with given inputs. The program counter starts at 0, and inputs are loaded into registers 0, 1, ....
  • Cslib.URM.ProgramA URM program is a list of instructions.
  • 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.from_toStandardFormReverse 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…
  • Cslib.URM.StepsMulti-step execution: the reflexive-transitive closure of Step.
  • Cslib.URM.State.isHaltedA state is halted if the program counter is at or beyond the program length.
  • Cslib.URM.Step.toStandardFormForward step correspondence: if p steps from s to s', then either: (1) p.toStandardForm steps from s to s' (same step), or (2) s' is…

Read back from the Lean

For every program p (of type Cslib.URM.Program) and every list of natural numbers inputs, p.toStandardForm halts on inputs if and only if p halts on inputs.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem reduces to the forward direction because the reverse direction was already established by urm_halts_toStandardForm_of_halts. The forward direction is proved by generalizing to all states that reach the final halted state in p.toStandardForm, and proceeding by head induction on the multi-step execution. In the base case, halting coincides because standard form preserves program length; in the inductive step, each transition in standard form either mimics a step in p or directly steps to a halted state.

  1. The equivalence reduces to the forward direction: if p.toStandardForm halts on inputs, then p halts on inputs.

    The theorem is an 'if and only if'. Line 5 provides the reverse direction directly from the previously proved lemma urm_halts_toStandardForm_of_halts, leaving only the forward implication.

    line 5

    uses urm_halts_toStandardForm_of_halts

      refine ⟨fun h => ?_, urm_halts_toStandardForm_of_halts p inputs⟩
  2. Assuming p.toStandardForm halts at state s_halt, it suffices to show that any state that can reach s_halt under p.toStandardForm also halts under p.

    Line 6 unpacks the assumption that p.toStandardForm halts on the inputs into an execution sequence from the initial state to a halted state s_halt. Lines 7–8 generalize the goal: if every state reaching s_halt under p.toStandardForm can reach a halted state under p, then applying this to the initial state proves that p halts.

    lines 6–8

      rcases h with ⟨s_halt, hsteps, hhalt⟩
      suffices ∀ s, Steps p.toStandardForm s s_halt → ∃ s', Steps p s s' ∧ s'.isHalted p from
        this (State.init inputs) hsteps
  3. The generalized claim is set up for proof by head induction on the execution sequence from s to s_halt in p.toStandardForm.

    Line 9 introduces an arbitrary state s and an execution path hs from s to s_halt under p.toStandardForm. Line 10 sets up induction on the first step of this path using Relation.ReflTransGen.head_induction_on, yielding a base case (zero steps, s = s_halt) and an inductive step (s steps to an intermediate state c).

    lines 9–10

    uses Relation.ReflTransGen.head_induction_on

      intro s hs
      induction hs using Relation.ReflTransGen.head_induction_on with
  4. In the base case (s = s_halt), s_halt is already halted under p.

    For s = s_halt, zero steps in p are needed by Relation.ReflTransGen.refl. By State.isHalted_iff, being halted means the program counter is at least the length of the program. Since Program.toStandardForm_length ensures p and p.toStandardForm have identical lengths, the fact that s_halt is halted under p.toStandardForm implies it is also halted under p.

    lines 11–13

    uses Relation.ReflTransGen.refl, State.isHalted_iff, Program.toStandardForm_length

      | refl =>
        refine ⟨s_halt, Relation.ReflTransGen.refl, ?_⟩
        rwa [State.isHalted_iff, ← Program.toStandardForm_length, ← State.isHalted_iff]
  5. In the inductive step, if s steps to c under p.toStandardForm and c halts under p, then s also halts under p.

    By Step.from_toStandardForm, the step s → c in p.toStandardForm falls into two cases: either it is also a valid step in p, so prepending it to the execution from c (provided by the induction hypothesis) via Relation.ReflTransGen.head reaches a halted state; or it represents a jump out of bounds in standard form, in which case p takes a single step via Relation.ReflTransGen.single to a state s₂ that is already halted under p.

    lines 14–18

    uses Step.from_toStandardForm, Relation.ReflTransGen.head, Relation.ReflTransGen.single

      | head hstep hrest ih =>
        rcases Step.from_toStandardForm hstep with h1 | ⟨_, s₂, hstep₂, hhalt₂, _⟩
        · rcases ih with ⟨s', hsteps', hhalt'⟩
          exact ⟨s', Relation.ReflTransGen.head h1 hsteps', hhalt'⟩
        · exact ⟨s₂, Relation.ReflTransGen.single hstep₂, hhalt₂⟩
urm_halts_toStandardForm_of_halts
If a URM program p halts on an input list, then its standard form p.toStandardForm also halts on that input list.
Relation.ReflTransGen.head_induction_on
Head-induction principle for the reflexive transitive closure of a relation: to prove a property of a path from a to b, it suffices to show it for the reflexive base case at b, and that prepending a single step a → c preserves the property.
Relation.ReflTransGen.refl
Every element is related to itself in zero steps in the reflexive transitive closure of a relation.
State.isHalted_iff
A state s is halted under program p if and only if its program counter is at least the length of p.
Program.toStandardForm_length
The standard form p.toStandardForm has the same number of instructions as p.
Step.from_toStandardForm
A step in p.toStandardForm from s to s' either is also a valid step in p, or s' is halted in p.toStandardForm and s steps in p to an already-halted state s₂ with the same registers as s'.
Relation.ReflTransGen.head
Prepending a single transition step to a multi-step sequence in the reflexive transitive closure yields a valid multi-step sequence.
Relation.ReflTransGen.single
A single transition step forms a path of length one in the reflexive transitive closure.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

open Cslib.URM in/-- A URM program halts on an input list if and only if its standard form halts on that input list. -/theorem urm_halts_toStandardForm (p : Program) (inputs : List ℕ) :    Halts p.toStandardForm inputs ↔ Halts p inputs := by  refine ⟨fun h => ?_, urm_halts_toStandardForm_of_halts p inputs⟩  rcases h with ⟨s_halt, hsteps, hhalt⟩  suffices ∀ s, Steps p.toStandardForm s s_halt → ∃ s', Steps p s s' ∧ s'.isHalted p from    this (State.init inputs) hsteps  intro s hs  induction hs using Relation.ReflTransGen.head_induction_on with  | refl =>    refine ⟨s_halt, Relation.ReflTransGen.refl, ?_⟩    rwa [State.isHalted_iff, ← Program.toStandardForm_length, ← State.isHalted_iff]  | head hstep hrest ih =>    rcases Step.from_toStandardForm hstep with h1 | ⟨_, s₂, hstep₂, hhalt₂, _⟩    · rcases ih with ⟨s', hsteps', hhalt'⟩      exact ⟨s', Relation.ReflTransGen.head h1 hsteps', hhalt'⟩    · exact ⟨s₂, Relation.ReflTransGen.single hstep₂, hhalt₂⟩
See it in the graphDiscuss this resultChallenge it