two_counter_machine_zero_test_step
def
The 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 counter vector is left unchanged.
Statement
def two_counter_machine_zero_test_step {Q : Type*} (M : TwoCounterMachine Q) (c₁ c₂ : Q × ℕ × ℕ) : Prop
- Source
- step towards symmetric_two_counter_boundary_reachability_semilinear
- Verified
- 20 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 1
- two_counter_machine_zero_test_state_reachq' is reachable from q by a sequence of zero tests while the counter vector is held fixed at p.
Lean source view module on GitHub
/-- The zero-test part of the one-step relation: only the control state can change, both counters are preserved. -/ def two_counter_machine_zero_test_step {Q : Type*} (M : TwoCounterMachine Q) (c₁ c₂ : Q × ℕ × ℕ) : Prop := ((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)