AFTD Auto-Formalizing Theoretical Domains

Cslib.URM.Step

inductiveimported Lean

Single-step execution relation for URMs. Each constructor corresponds to one of the four instruction types: - zero: Execute Z n (set register n to 0) - succ: Execute S n (increment register n) - transfer: Execute T m n (copy register m to register n) - jump_eq: Execute J m n q when registers m and n are equal (jump to q) - jump_ne: Execute J m n q when registers m and n differ (proceed to next)

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
variable (p : Program) in
@[grind]
inductive Cslib.URM.Step : State → State → Prop
Defined in
CSLib, `Cslib.URM.Step`
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
none listed
Built on 8
Used by 14

Lean source view module on GitHub

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
variable (p : Program) in
/-- Single-step execution relation for URMs. Each constructor corresponds to one of the four instruction types: - `zero`: Execute `Z n` (set register n to 0) - `succ`: Execute `S n` (increment register n) - `transfer`: Execute `T m n` (copy register m to register n) - `jump_eq`: Execute `J m n q` when registers m and n are equal (jump to q) - `jump_ne`: Execute `J m n q` when registers m and n differ (proceed to next) -/
@[grind]
inductive Cslib.URM.Step : State → State → Prop where
  | zero {s : State} {n : ℕ}
      (h : p[s.pc]? = some (Instr.Z n)) :
      Step s ⟨s.pc + 1, s.regs.write n 0⟩
  | succ {s : State} {n : ℕ}
      (h : p[s.pc]? = some (Instr.S n)) :
      Step s ⟨s.pc + 1, s.regs.write n (s.regs.read n + 1)⟩
  | transfer {s : State} {m n : ℕ}
      (h : p[s.pc]? = some (Instr.T m n)) :
      Step s ⟨s.pc + 1, s.regs.write n (s.regs.read m)⟩
  | jump_eq {s : State} {m n q : ℕ}
      (h : p[s.pc]? = some (Instr.J m n q))
      (heq : s.regs.read m = s.regs.read n) :
      Step s ⟨q, s.regs⟩
  | jump_ne {s : State} {m n q : ℕ}
      (h : p[s.pc]? = some (Instr.J m n q))
      (hne : s.regs.read m ≠ s.regs.read n) :
      Step s ⟨s.pc + 1, s.regs⟩
See it in the graphDiscuss this resultChallenge it