TwoCounterInstr
inductive
An 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 second counter.
Statement
inductive TwoCounterInstr where
- Defined in
- arXiv:2610.23495, Section 2
- Verified
- 19 Oct 2026
- Axioms
- none listed
- Used by 12
- 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…
- TwoCounterMachineA structure TwoCounterMachine parameterized by a type of control states Q : Type*, consisting of a single field transitions which is a…
- 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_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
An inductive type TwoCounterInstr with three constructors:
- update (w₁ w₂ : ℤ): takes two integers w₁ and w₂ and produces an instruction,
- zeroTest₁: produces an instruction with no arguments,
- zeroTest₂: produces an instruction with no arguments.
It derives decidable equality (DecidableEq).
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
/-- Instructions for a 2-counter machine: vector update or zero-test on either counter. -/ inductive TwoCounterInstr where | update (w₁ w₂ : ℤ) : TwoCounterInstr | zeroTest₁ : TwoCounterInstr | zeroTest₂ : TwoCounterInstr deriving DecidableEq