Abelian logic gates
arXiv:1511.00422 · doi:10.1017/S0963548318000482
Abstract
An abelian processor is an automaton whose output is independent of the order of its inputs. Bond and Levine have proved that a network of abelian processors performs the same computation regardless of processing order (subject only to a halting condition). We prove that any finite abelian processor can be emulated by a network of certain very simple abelian processors, which we call gates. The most fundamental gate is a "toppler", which absorbs input particles until their number exceeds some given threshold, at which point it topples, emitting one particle and returning to its initial state. With the exception of an adder gate, which simply combines two streams of particles, each of our gates has only one input wire. Our results can be reformulated in terms of the functions computed by processors, and one consequence is that any increasing function from N^k to N^l that is the sum of a linear function and a periodic function can be expressed in terms of (possibly nested) sums of floors of quotients by integers.
arXiv comment35 pages, many figures. v2 revised for referee comments, to appear in Combinatorics, Probability and Computing
References in corpus (10)
- The abelian sandpile and related models
- Chip-Firing and Rotor-Routing on Directed Graphs
- Strong Spherical Asymptotics for Rotor-Router Aggregation and the Divisible Sandpile
- The Computational Complexity of Sandpiles
- Growth Rates and Explosions in Sandpiles
- Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph
- Pattern formation in fast-growing sandpiles
- Rotor-routing and spanning trees on planar graphs
- On the complexity of the chip-firing reachability problem
- Some halting problems for abelian sandpiles are undecidable in dimension three