AFTD Auto-Formalizing Theoretical Domains

two_counter_machine_zero_test_step

def

The zero-test one-step relation of a 2-counter machine M: a zero test on counter i is taken (which requires counter i to be 0) and the counter vector is left unchanged.

Statement

def two_counter_machine_zero_test_step {Q : Type*} (M : TwoCounterMachine Q) (c₁ c₂ : Q × ℕ × ℕ) : Prop
Source
step towards symmetric_two_counter_boundary_reachability_semilinear
Verified
20 Oct 2026
Axioms
none listed
Built on 2
  • TwoCounterInstrAn instruction of a 2-counter machine is either an update by a vector of integers (w₁, w₂), or a zero-test on the first counter or the…
  • TwoCounterMachineA structure TwoCounterMachine parameterized by a type of control states Q : Type*, consisting of a single field transitions which is a…
Used by 1

Lean source view module on GitHub

/-- The zero-test part of the one-step relation: only the control state can change, both counters are preserved. -/
def two_counter_machine_zero_test_step {Q : Type*} (M : TwoCounterMachine Q) (c₁ c₂ : Q × ℕ × ℕ) : Prop :=
  ((c₁.1, TwoCounterInstr.zeroTest₁, c₂.1) ∈ M.transitions ∧ c₁.2.1 = 0 ∧ c₂.2 = c₁.2) ∨
  ((c₁.1, TwoCounterInstr.zeroTest₂, c₂.1) ∈ M.transitions ∧ c₁.2.2 = 0 ∧ c₂.2 = c₁.2)
See it in the graphDiscuss this resultChallenge it