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
- op_360_single_counter_update_strictly_less_expressiveThere exists a symmetric 2-counter machine M over a finite state type Q and states q, q' in Q whose reachability relation…
- single_counter_symmetric_cannot_match_diag_reachNo finite-state symmetric 2-counter machine with single-counter updates can have reachability relation equal to that of the diagonal…
- diag_two_counter_machine_is_symmetricThe 2-counter machine over Bool with a single update (1, 1) from false to true is symmetric.
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