AFTD Auto-Formalizing Theoretical Domains

op_360_single_counter_update_strictly_less_expressive

theoremverifiedformalization

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

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.

  1. 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.

    lines 7–8

    uses diag_two_counter_machine_is_symmetric

      refine ⟨Bool, inferInstance, ⟨{(false, TwoCounterInstr.update 1 1, true)}⟩,
        diag_two_counter_machine_is_symmetric, false, true, ?_⟩
  2. 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.

    lines 9–10

    uses single_counter_symmetric_cannot_match_diag_reach

      intro 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

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