A1 Refereed original research article in a scientific journal
Universal gates with wires in a row
Authors: Salo Ville
Publisher: Springer
Publication year: 2022
Journal: Journal of Algebraic Combinatorics
Journal acronym: J ALGEBR COMB
Volume: 55
Issue: 2
First page : 335
Last page: 353
Number of pages: 19
ISSN: 0925-9899
eISSN: 1572-9192
DOI: https://doi.org/10.1007/s10801-021-01053-7
Web address : https://link.springer.com/article/10.1007%2Fs10801-021-01053-7
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/67531805
Abstract
We give some optimal size generating sets for the group generated by shifts and local permutations on the binary full shift. We show that a single generator, namely the fully asynchronous application of the elementary cellular automaton 57 (or, by symmetry, ECA 99), suffices in addition to the shift. In the terminology of logical gates, we have a single reversible gate whose shifts generate all (finitary) reversible gates on infinitely many binary-valued wires that lie in a row and cannot (a priori) be rearranged. We classify pairs of words u, v such that the gate swapping these two words, together with the shift and the bit flip, generates all local permutations. As a corollary, we obtain analogous results in the case where the wires are arranged on a cycle, confirming a conjecture of Macauley-McCammond-Mortveit and Vielhaber.
We give some optimal size generating sets for the group generated by shifts and local permutations on the binary full shift. We show that a single generator, namely the fully asynchronous application of the elementary cellular automaton 57 (or, by symmetry, ECA 99), suffices in addition to the shift. In the terminology of logical gates, we have a single reversible gate whose shifts generate all (finitary) reversible gates on infinitely many binary-valued wires that lie in a row and cannot (a priori) be rearranged. We classify pairs of words u, v such that the gate swapping these two words, together with the shift and the bit flip, generates all local permutations. As a corollary, we obtain analogous results in the case where the wires are arranged on a cycle, confirming a conjecture of Macauley-McCammond-Mortveit and Vielhaber.
Downloadable publication This is an electronic reprint of the original article. |  |
UTU Research Portal