
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, which sends letters (‘particles’) from a unary alphabet. Our results can be reformulated in terms of the functions computed by processors, and one consequence is that any increasing function from ℕk to ℕℓ 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.
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Formal Languages and Automata Theory (cs.FL), Computer Science - Formal Languages and Automata Theory, 68Q10, 68Q45, 68Q85, 90B10, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Formal Languages and Automata Theory (cs.FL), Computer Science - Formal Languages and Automata Theory, 68Q10, 68Q45, 68Q85, 90B10, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Computer Science - Discrete Mathematics
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
