AFTD Auto-Formalizing Theoretical Domains

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

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₂
See it in the graphDiscuss this resultChallenge it