AFTD Auto-Formalizing Theoretical Domains

two_counter_machine_step

def

The one-step transition relation of a 2-counter machine M between configurations c₁ and c₂ in Q × (ℕ × ℕ): either an update transition from c₁.1 to c₂.1 with displacement (w₁, w₂) modifies the counters by (w₁, w₂), or a zero-test transition on counter 1 occurs when counter 1 is 0 and leaves counters unchanged, or a zero-test transition on counter 2 occurs when counter 2 is 0 and leaves counters unchanged.

Statement

def two_counter_machine_step {Q : Type*} (M : TwoCounterMachine Q) (c₁ c₂ : Q × (ℕ × ℕ)) : Prop
Defined in
arXiv:2610.23495, Sec. 2
Verified
19 Oct 2026
Axioms
none listed
Built on 2
  • 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…
  • TwoCounterMachineA structure TwoCounterMachine parameterized by a type of control states Q : Type*, consisting of a single field transitions which is a…
Used by 4

Read back from the Lean

Given a type Q, a two-counter machine M (having a finite set of transitions M.transitions of triples (state, instruction, state)), and two configurations c₁, c₂ : Q × (ℕ × ℕ) (each consisting of a state in Q and values for two counters in ℕ): two_counter_machine_step M c₁ c₂ is defined as the disjunction of three cases: 1. There exist integers w₁, w₂ : ℤ such that (c₁.1, TwoCounterInstr.update w₁ w₂, c₂.1) ∈ M.transitions, (c₁.2.1 : ℤ) + w₁ = (c₂.2.1 : ℤ), and (c₁.2.2 : ℤ) + w₂ = (c₂.2.2 : ℤ). 2. (c₁.1, TwoCounterInstr.zeroTest₁, c₂.1) ∈ M.transitions, the first counter of c₁ is zero (c₁.2.1 = 0), and the counter values of c₂ equal those of c₁ (c₂.2 = c₁.2). 3. (c₁.1, TwoCounterInstr.zeroTest₂, c₂.1) ∈ M.transitions, the second counter of c₁ is zero (c₁.2.2 = 0), and the counter values of c₂ equal those of c₁ (c₂.2 = c₁.2).

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

/-- One-step transition relation between configurations of a 2-counter machine. -/
def two_counter_machine_step {Q : Type*} (M : TwoCounterMachine Q) (c₁ c₂ : Q × (ℕ × ℕ)) : Prop :=
  (∃ w₁ w₂ : ℤ,
    (c₁.1, TwoCounterInstr.update w₁ w₂, c₂.1) ∈ M.transitions ∧
    (c₁.2.1 : ℤ) + w₁ = c₂.2.1 ∧ (c₁.2.2 : ℤ) + w₂ = c₂.2.2) ∨
  ((c₁.1, TwoCounterInstr.zeroTest₁, c₂.1) ∈ M.transitions ∧
    c₁.2.1 = 0 ∧ c₂.2 = c₁.2) ∨
  ((c₁.1, TwoCounterInstr.zeroTest₂, c₂.1) ∈ M.transitions ∧
    c₁.2.2 = 0 ∧ c₂.2 = c₁.2)
See it in the graphDiscuss this resultChallenge it