two_counter_machine_reach_rel
For 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 set of pairs of counter vectors (u, v) in (ℕ × ℕ) × (ℕ × ℕ) such that configuration (q', v) is reachable from configuration (q, u) under the reflexive-transitive closure of the step relation of M.
Statement
def two_counter_machine_reach_rel {Q : Type*} (M : TwoCounterMachine Q) (q q' : Q) : Set ((ℕ × ℕ) × (ℕ × ℕ))
- Defined in
- arXiv:2610.23495, Sec. 1 and Sec. 3
- Verified
- 19 Oct 2026
- Axioms
- none listed
- Built on 2
- 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…
- Used by 3
- 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_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
Given a type Q, a two-counter machine M : TwoCounterMachine Q, and states q, q' : Q, two_counter_machine_reach_rel M q q' is defined as the set of pairs of counter values (c, c') : (ℕ × ℕ) × (ℕ × ℕ) such that the configuration (q', c') is reachable from (q, c) by zero or more transition steps of M (that is, in the reflexive-transitive closure Relation.ReflTransGen of two_counter_machine_step M).
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
/-- The reachability relation between pairs of counter vectors for fixed control states in a 2-counter machine. -/ def two_counter_machine_reach_rel {Q : Type*} (M : TwoCounterMachine Q) (q q' : Q) : Set ((ℕ × ℕ) × (ℕ × ℕ)) := { p | Relation.ReflTransGen (two_counter_machine_step M) (q, p.1) (q', p.2) }