Abelian logic gates

DOI10.1017/S0963548318000482zbMATH Open1433.68138arXiv1511.00422OpenAlexW2269722460WikidataQ128233940 ScholiaQ128233940MaRDI QIDQ5222545FDOQ5222545

Authors: A. E. Holroyd, Lionel Levine, Peter Winkler 

Publication date: 6 April 2020

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1511.00422

Recommendations

• Abelian networks. I: Foundations and examples
• scientific article; zbMATH DE number 56705
• Abelian networks. II: Halting on all inputs
• The Parallel Complexity of Abelian Permutation Group Problems
• Abelian networks IV. Dynamics of nonhalting networks

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Networks and circuits as models of computation; circuit complexity (68Q06)

Cites Work

• Self-organized critical state of sandpile automaton models
• On the ranks of configurations on the complete graph
• Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile
• Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs
• CoEulerian graphs
• Rotor walks and Markov chains
• Chip-Firing and Rotor-Routing on Directed Graphs
• Abelian networks. I: Foundations and examples
• Abelian networks. III: The critical group
• Abelian networks. II: Halting on all inputs
• Patterns formed by addition of grains to only one site of an Abelian sandpile
• Title not available (Why is that?)
• Growth rates and explosions in sandpiles
• Pattern formation in growing sandpiles with multiple sources or sinks
• The computational complexity of sandpiles
• Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph
• On the complexity of sandpile prediction problems
• Polynomial Bound for a Chip Firing Game on Graphs
• On the complexity of sandpile critical avalanches
• Some halting problems for abelian sandpiles are undecidable in dimension three
• On the complexity of the chip-firing reachability problem
• Rotor-routing and spanning trees on planar graphs

Cited In (10)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Interference-based logic gates
• Few Product Gates But Many Zeros
• Abelian networks. II: Halting on all inputs
• Sorting via chip-firing
• Elementary gates for cartoon computation
• Abelian networks. I: Foundations and examples
• Abelian networks IV. Dynamics of nonhalting networks
• Sorting via chip-firing

This page was built for publication: Abelian logic gates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5222545)