AFTD Auto-Formalizing Theoretical Domains

two_counter_machine_is_symmetric

def

A 2-counter machine M with state type Q is symmetric if for every update transition from q to q' with integer weights (w₁, w₂), the machine also contains the update transition from q to q' with swapped weights (w₂, w₁).

Statement

def two_counter_machine_is_symmetric {Q : Type*} (M : TwoCounterMachine Q) : Prop
Defined in
arXiv:2610.23495, Sec. 2
Verified
19 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 3

Read back from the Lean

For a type Q and a two-counter machine M : TwoCounterMachine Q, two_counter_machine_is_symmetric M asserts that for all states q, q' : Q and all integers w₁, w₂ : ℤ, if the transition (q, TwoCounterInstr.update w₁ w₂, q') is in M.transitions, then the transition (q, TwoCounterInstr.update w₂ w₁, q') is also in M.transitions.

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

Lean source view module on GitHub

/-- Predicate asserting that a 2-counter machine is symmetric under swapping the two counters. -/
def two_counter_machine_is_symmetric {Q : Type*} (M : TwoCounterMachine Q) : Prop :=
  ∀ q q' : Q, ∀ w₁ w₂ : ℤ,
    (q, TwoCounterInstr.update w₁ w₂, q') ∈ M.transitions →
    (q, TwoCounterInstr.update w₂ w₁, q') ∈ M.transitions
See it in the graphDiscuss this resultChallenge it