pipette
ESEspañol

Symmetric two-counter machines

Krzysztof Jaros, {\L}ukasz Kami\'nski, Maja K\k{a}dzio{\l}ka, S{\l}awomir Lasota

Preprint

In the authors' words

Counter machines are a particularly simple, Turing-complete model of computation. We study the expressive power of nondeterministic 2-counter machines which are symmetric, in that their set of update transitions is invariant under swapping of counters. Our model is an extension of symmetric 2-VASS, in that we allow modifying both counters within a single transition. As the main result we demonstrate a dramatic impact of symmetry: we show that symmetric 2-counter machines are not Turing-complete, by proving decidability of their reachability problem. We conjecture that the decidability extends to machines with 3 or more counters that are symmetric, meaning the set of update transitions is invariant under any permutation of counters. We leave this problem open for machines with 3 and more counters, while identifying a frontier of the impact of symmetry: we prove undecidability for 3-counter machines invariant under the cyclic permutation group of order 3.

Main resultLimitation the authors admit

Appeared: Monday, October 19. arXiv. Preprint, not yet peer-reviewed.