two_counter_machine_step
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
- 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).
- single_counter_step_preserves_one_coordIn any single step of a 2-counter machine with single-counter updates, at least one counter remains unchanged.
- 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_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…
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)