op_360_single_counter_update_strictly_less_expressive
There exists a symmetric 2-counter machine M over a finite state type Q and states q, q' in Q whose reachability relation two_counter_machine_reach_rel M q q' cannot be realized as the reachability relation two_counter_machine_reach_rel M' q0 q1 between any states q0, q1 of any finite-state symmetric 2-counter machine M' with single-counter updates.
Statement
theorem op_360_single_counter_update_strictly_less_expressive : ∃ (Q : Type) (_ : Finite Q) (M : TwoCounterMachine Q) (_ : two_counter_machine_is_symmetric M) (q q' : Q), ∀ (Q' : Type) (_ : Finite Q') (M' : TwoCounterMachine Q') (_ : two_counter_machine_is_symmetric M') (_ : two_counter_machine_is_single_counter_update M') (q0 q1 : Q'), two_counter_machine_reach_rel M' q0 q1 ≠ two_counter_machine_reach_rel M q q'
- Formalizes
- scout/2610-23495-symmetric-two-counter-machines.md:304
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- two_counter_machine_is_symmetricA 2-counter machine M with state type Q is symmetric if for every update transition from q to q' with integer weights (w₁, w₂), the…
- two_counter_machine_is_single_counter_updateA 2-counter machine M with state type Q has single-counter updates if for every update transition from q to q' with displacements (w₁,…
- 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…
- single_counter_step_preserves_one_coordIn any single step of a 2-counter machine with single-counter updates, at least one counter remains unchanged.
- diag_two_counter_machine_is_symmetricThe 2-counter machine over Bool with a single update (1, 1) from false to true is symmetric.
- 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_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…
- 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…
Read back from the Lean
There exist a finite state type $Q$ (in Type 0), a two-counter machine $M$ over $Q$ whose counter-update transitions are symmetric (whenever $(q, \text{update}(w_1, w_2), q') \in M.\text{transitions}$, the swapped transition $(q, \text{update}(w_2, w_1), q')$ is also in $M.\text{transitions}$), and states $q, q' \in Q$, such that:
for every finite state type $Q'$ (in Type 0), every two-counter machine $M'$ over $Q'$, if $M'$ has symmetric counter-update transitions and all its update transitions update at most one counter (for every $(q_a, \text{update}(w_1, w_2), q_b) \in M'.\text{transitions}$, $w_1 = 0 \lor w_2 = 0$), then for all states $q_0, q_1 \in Q'$,
the counter reachability relation from $q_0$ to $q_1$ in $M'$ does not equal the counter reachability relation from $q$ to $q'$ in $M$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof shows that unrestricted symmetric 2-counter machines are strictly more expressive than their single-counter update fragment by providing an explicit counterexample machine M on the two-state type Bool. The machine M has a single transition from false to true that increments both counters simultaneously by 1, which is symmetric because the update vector (1, 1) is unchanged when swapping the counters. The claim then concludes by applying the existing theorem single_counter_symmetric_cannot_match_diag_reach, which proves that no finite-state symmetric machine using only single-counter updates can reproduce this diagonal increment reachability relation.
It suffices to show that the reachability relation of the machine on Bool with the diagonal transition (false, update 1 1, true) cannot be matched by any symmetric single-counter-update machine.
We witness the existential quantifier by choosing the finite state type Q = Bool, states q = false and q' = true, and the machine M with the single transition that increments both counters by 1 simultaneously from false to true. Since the update (1, 1) is invariant under swapping the two counters, M is symmetric, as stated by diag_two_counter_machine_is_symmetric.
uses
diag_two_counter_machine_is_symmetricrefine ⟨Bool, inferInstance, ⟨{(false, TwoCounterInstr.update 1 1, true)}⟩, diag_two_counter_machine_is_symmetric, false, true, ?_⟩No symmetric single-counter-update machine M' on a finite state type Q' can realize the reachability relation between false and true of M.
We introduce an arbitrary finite state type Q', a symmetric machine M' with single-counter updates, and states q0, q1 ∈ Q'. The result single_counter_symmetric_cannot_match_diag_reach directly proves that the reachability relation between q0 and q1 in M' is not equal to the reachability relation between false and true in M.
uses
single_counter_symmetric_cannot_match_diag_reachintro Q' hQ' M' hsymm hsc q0 q1 exact single_counter_symmetric_cannot_match_diag_reach Q' hQ' M' hsymm hsc q0 q1
diag_two_counter_machine_is_symmetric- The two-counter machine on state type Bool whose sole transition is (false, update 1 1, true) is symmetric.
single_counter_symmetric_cannot_match_diag_reach- For any finite state type Q' and any symmetric two-counter machine M' using only single-counter updates, the reachability relation between any two states q0 and q1 cannot equal that of the diagonal machine on Bool between false and true.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Open Problem OP-360: The single-counter update fragment of symmetric 2-counter machines is strictly less expressive in terms of reachability relations than unrestricted symmetric 2-counter machines. -/theorem op_360_single_counter_update_strictly_less_expressive : ∃ (Q : Type) (_ : Finite Q) (M : TwoCounterMachine Q) (_ : two_counter_machine_is_symmetric M) (q q' : Q), ∀ (Q' : Type) (_ : Finite Q') (M' : TwoCounterMachine Q') (_ : two_counter_machine_is_symmetric M') (_ : two_counter_machine_is_single_counter_update M') (q0 q1 : Q'), two_counter_machine_reach_rel M' q0 q1 ≠ two_counter_machine_reach_rel M q q' := by refine ⟨Bool, inferInstance, ⟨{(false, TwoCounterInstr.update 1 1, true)}⟩, diag_two_counter_machine_is_symmetric, false, true, ?_⟩ intro Q' hQ' M' hsymm hsc q0 q1 exact single_counter_symmetric_cannot_match_diag_reach Q' hQ' M' hsymm hsc q0 q1