Universal gates with wires in a row

DOI10.1007/S10801-021-01053-7zbMATH Open1494.37011arXiv1809.08050OpenAlexW3204048216MaRDI QIDQ2114796FDOQ2114796

Yanyan Li

Publication date: 15 March 2022

Published in: Journal of Algebraic Combinatorics (Search for Journal in Brave)

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.

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

zbMATH Keywords

reversible gatesLEF groupsrule 57

Mathematics Subject Classification ID

Quantum computation (81P68) Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80) Operations and polynomials in algebraic structures, primal algebras (08A40) Networks and circuits as models of computation; circuit complexity (68Q06)

Cites Work

• Title not available (Why is that?)
• Statistical mechanics of cellular automata
• The Group of Reversible Turing Machines
• Cellular Automata and Groups
• Solution of Two Conjectures in Symbolic Dynamics
• Dynamics groups of asynchronous cellular automata
• Towards an algebraic theory of Boolean circuits.
• The Classification of Reversible Bit Operations
• Strongly Universal Reversible Gate Sets
• Closed Systems of Invertible Maps

Cited In (3)

• On the action of the toggle group of the Dynkin diagram of type \(A\)
• Gate lattices and the stabilized automorphism group
• Liftings of automorphisms of hypermaps

This page was built for publication: Universal gates with wires in a row

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