urm_halts_toStandardForm
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: ExecuteZ 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…
- Cslib.URM.HaltsA program halts on given inputs if execution reaches a halted state. This is equivalent to
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.
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.
uses
urm_halts_toStandardForm_of_haltsrefine ⟨fun h => ?_, urm_halts_toStandardForm_of_halts p inputs⟩
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.
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
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).
uses
Relation.ReflTransGen.head_induction_onintro s hs induction hs using Relation.ReflTransGen.head_induction_on with
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.
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]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.
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
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.
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₂⟩