TwoCounterMachine
structure
A structure TwoCounterMachine parameterized by a type of control states Q : Type*, consisting of a single field transitions which is a finite set of triples (q, instr, q') with q, q' ∈ Q and instr ∈ TwoCounterInstr.
Statement
structure TwoCounterMachine (Q : Type*) where
- Defined in
- arXiv:2610.23495, Section 2
- Verified
- 19 Oct 2026
- Axioms
- none listed
- Built on 1
- 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 13
- diag_two_counter_machine_reach_rel_iffThe reachability relation of the diagonal machine between false and true consists exactly of pairs (u, v) with v = (u.1 + 1, u.2 + 1).
- 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.
- two_counter_machine_is_single_counter_updateA 2-counter machine M with state type Q has single-counter updates if for every update transition from q to q' with displacements (w₁,…
- 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…
- two_counter_machine_stepThe one-step transition relation of a 2-counter machine M between configurations c₁ and c₂ in Q × (ℕ × ℕ): either an update transition…
- two_counter_machine_reach_relFor a 2-counter machine M with state type Q and states q, q' in Q, the reachability relation two_counter_machine_reach_rel M q q' is the…
- two_counter_machine_is_symmetricA 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…
- two_counter_machine_zero_test_state_reachq' is reachable from q by a sequence of zero tests while the counter vector is held fixed at p.
- two_counter_machine_zero_test_stepThe 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…
- two_counter_machine_is_vassA 2-counter machine M is a vector addition system with states (2-VASS) if every transition in M.transitions is an update transition.
- two_counter_machine_update_stepThe zero-test-free (update-only) one-step relation of a 2-counter machine M: an update transition from c₁.1 to c₂.1 with integer…
- 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
A structure TwoCounterMachine parameterized by a type of states Q : Type*, containing a single field transitions which is a finite set (Finset) of triples (q, instr, q') where q, q' : Q and instr is a TwoCounterInstr.
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 structure parameterized by a type of control states Q, consisting of a finite set of transitions labelled by 2-counter instructions. -/ structure TwoCounterMachine (Q : Type*) where transitions : Finset (Q × TwoCounterInstr × Q)