two_counter_machine_is_single_counter_update
def
A 2-counter machine M with state type Q has single-counter updates if for every update transition from q to q' with displacements (w₁, w₂), the displacement vector satisfies IsSingleCounterUpdate w₁ w₂.
Statement
def two_counter_machine_is_single_counter_update {Q : Type*} (M : TwoCounterMachine Q) : Prop
- Defined in
- scout/2610-23495-symmetric-two-counter-machines.md:1692
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Built on 3
- IsSingleCounterUpdateA pair of integer displacements (w₁, w₂) is a single-counter update if at least one coordinate is zero, that is, w₁ = 0 or w₂ = 0.
- TwoCounterMachineA structure TwoCounterMachine parameterized by a type of control states Q : Type*, consisting of a single field transitions which is a…
- 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…
- 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_step_preserves_one_coordIn any single step of a 2-counter machine with single-counter updates, at least one counter remains unchanged.
- 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…
Read back from the Lean
For a two-counter machine $M$ with state type $Q$, this definition asserts that for all states $q, q' : Q$ and all integers $w_1, w_2 : \mathbb{Z}$, if the transition $(q, \text{TwoCounterInstr.update}(w_1, w_2), q')$ is in $M$'s finite set of transitions, then $(w_1, w_2)$ is a single counter update (at least one of $w_1 = 0$ or $w_2 = 0$).
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
/-- A 2-counter machine is single-counter update if every update transition modifies at most one counter. -/ def two_counter_machine_is_single_counter_update {Q : Type*} (M : TwoCounterMachine Q) : Prop := ∀ q q' : Q, ∀ w₁ w₂ : ℤ, (q, TwoCounterInstr.update w₁ w₂, q') ∈ M.transitions → IsSingleCounterUpdate w₁ w₂