urm_halts_toStandardForm_of_halts
If a URM program p halts on inputs, then its standard form p.toStandardForm halts on inputs.
Statement
open Cslib.URM in theorem urm_halts_toStandardForm_of_halts (p : Program) (inputs : List ℕ) (h : Halts p inputs) : Halts p.toStandardForm inputs
- Source
- Cutland, Computability: An Introduction to Recursive Function Theory
- Verified
- 12 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 13
- 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.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.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.Program.toStandardFormConvert a program to standard form by capping all jump targets at the program length.
- 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.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.HaltsA program halts on given inputs if execution reaches a halted state. This is equivalent to
- Used by 1
- urm_halts_toStandardFormFor any URM program p and input list inputs, p halts on inputs if and only if its standard form p.toStandardForm halts on inputs.
Read back from the Lean
For any program p : Cslib.URM.Program and any list of natural numbers inputs : List ℕ, if p halts on inputs (Cslib.URM.Halts p inputs), then the standard-form version of p (p.toStandardForm) also halts on inputs (Cslib.URM.Halts p.toStandardForm 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
To prove that p.toStandardForm halts whenever p halts, we generalize the claim to all states that can reach the halting state of p and argue by head-induction along the execution path. In the base case of zero steps, the terminal state is already halted under p.toStandardForm because standard form preserves program length. In the inductive step, Step.toStandardForm ensures that each transition of p is either directly simulated by p.toStandardForm or replaced by a single step directly into a halted state.
It suffices to show that any state from which p can reach the terminal state s_halt also reaches a halted state under p.toStandardForm.
From the assumption that p halts on the given inputs, we obtain a terminal state s_halt reachable from State.init inputs that is halted under p. We generalize the goal to prove that every state s reaching s_halt under p can reach some halted state under p.toStandardForm; instantiating this claim with the initial state State.init inputs yields the theorem.
rcases h with ⟨s_halt, hsteps, hhalt⟩ suffices ∀ s, Steps p s s_halt → ∃ s', Steps p.toStandardForm s s' ∧ s'.isHalted p.toStandardForm from this (State.init inputs) hsteps
The generalized claim reduces to verifying a zero-step base case and an induction step for prepending an execution step.
We fix an arbitrary state s that reaches s_halt in some sequence of steps hs. Performing head-induction on this reflexive-transitive step relation using Relation.ReflTransGen.head_induction_on decomposes the path into the base case where s = s_halt (zero steps) and the inductive step where an initial step s → c is followed by a path c →* s_halt satisfying the induction hypothesis.
uses
Relation.ReflTransGen.head_induction_onintro s hs induction hs using Relation.ReflTransGen.head_induction_on with
When s = s_halt, the state is already halted under p.toStandardForm in zero steps.
In zero steps (via Relation.ReflTransGen.refl), the state remains s_halt. By State.isHalted_iff, a state is halted if and only if its program counter is at least the length of the program. Since Program.toStandardForm_length states that p.toStandardForm has the same length as p, s_halt being halted under p implies it is also halted under p.toStandardForm.
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]If s steps to c and c reaches s_halt, then s reaches a halted state under p.toStandardForm.
We analyze the first step s → c using Step.toStandardForm. In the first case, p.toStandardForm can perform the exact same transition s → c; prepending this step to the execution path from c to a halted state s' provided by the induction hypothesis (using Relation.ReflTransGen.head) shows that s halts. In the second case, Step.toStandardForm provides a direct single-step transition from s to a state s₂ that is already halted under p.toStandardForm, which yields a one-step halting execution path (using Relation.ReflTransGen.single).
uses
Step.toStandardForm,Relation.ReflTransGen.head,Relation.ReflTransGen.single| head hstep hrest ih => rcases Step.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₂⟩
Relation.ReflTransGen.head_induction_on- Induction on a path in the reflexive-transitive closure: to prove a property holds for a path from a to b, it suffices to prove it for the empty path at b, and that it is preserved when prepending a single step a → c before a path from c to b.
Relation.ReflTransGen.refl- The reflexive-transitive closure of any relation is reflexive; every state can reach itself in zero steps.
State.isHalted_iff- A state 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 of a program has the same number of instructions as the original program.
Step.toStandardForm- A single step s → s' of program p is either also a step of p.toStandardForm, or s' is halted under p and p.toStandardForm can step from s in one step to a state that is halted under p.toStandardForm.
Relation.ReflTransGen.head- Prepending a single transition a → b to a path from b to c in the reflexive-transitive closure yields a path from a to c.
Relation.ReflTransGen.single- A single transition a → b yields a one-step path 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/-- If a URM program halts on an input list, then its standard form also halts on that input list. -/theorem urm_halts_toStandardForm_of_halts (p : Program) (inputs : List ℕ) (h : Halts p inputs) : Halts p.toStandardForm inputs := by rcases h with ⟨s_halt, hsteps, hhalt⟩ suffices ∀ s, Steps p s s_halt → ∃ s', Steps p.toStandardForm s s' ∧ s'.isHalted p.toStandardForm 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.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₂⟩