AFTD Auto-Formalizing Theoretical Domains

two_counter_machine_reach_rel

def

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

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