Universal gates with wires in a row
Consider the Cantor set \(X=\{0,1\}^{\mathbb Z}\) with elements \((x_i)_i\), and the group \(G\) acting on \(X\) and generated by the shift map \(\sigma(x)=(x_{i+1})_i\) and all homeomorphisms \(f\colon X\to X\) with \textit{bounded support} in the sense \(f(x)_i=x_i\) whenever \(|i|>r(f)\). Such homeomorphisms are called \textit{invertible gates}, and a set of gates \(F\) is \textit{universal} if \(G=\langle F,\sigma\rangle\). The interpretation as gates is naturally motivated by electronics. For example, \(s(x)_i=\{x_{1-i}\text{ if }i\in\{0,1\},x_i\text{ else}\}\) is the \textit{swap} of two wires \(0,1\), and \(c^k(x)_i=\{1-x_0\text{ if }i=0\wedge x_1=\cdots=x_k=1,x_i\text{ else}\}\) is the \textit{\(k\)-th controlled NOT}. A set of gates \(F\) is universal precisely when every circuit relying on inputs arranged in a line may be expressed using \(F\) and its shifts. The author proves a collection of impressive results in two directions: firstly, about the group \(G\) itself. This is generated by \(\{s,c^0,c^2,\sigma\}\), meaning that \(\{s,c^0,c^2\}\) is universal; and it is even generated by \(\{f,\sigma\}\) for some specific gates \(f\) such as ``rule 57 (\(e^{57}(x)_0=1-x_0\) unless \(x_{-1}=0\ne x_1\), and no other input is changed). Secondly, he shows that these results on infinite groups have consequences for finite circuits with inputs arranged in a cycle. Let \(G_n\) denote the alternating group \(\operatorname{Alt}(\{0,1\}^n)\); then there is no homomorphism \(G\to G_n\), but nevertheless for every \(f\in G\) there is for all \(n\gg0\) a well-defined corresponding element \(f_n\in G_n\), which is asymptotically an injective homomorphism, mapping \(\sigma\) to the cyclic permutation \(\sigma_n\) of \(n\) bits. Said more compactly, the \((G_n)_n\), with the partially-defined map \(f\mapsto f_n\), confirms the fact that \(G\) is a \textit{LEF group}: every finite subset may be embedded into a finite group. Theorem~1 then shows that for \(F\) universal we have \(G_n=\langle F_n,\sigma_n\rangle\) for all \(n\ge n(F)\). In particular, \(G_n=\langle e^{57}_n,\sigma_n\rangle\) for all \(n\ge4\); this solves a conjecture by \textit{M. Macauley} et al. [J. Algebr. Comb. 33, No. 1, 11--35 (2011; Zbl 1211.37014)] and \textit{M. Vielhaber} [in: 18th international workshop on cellular automata and discrete complex systems and 3rd international symposium Journées Automates Cellulaires, La Marana, Corsica, September 19--21, 2012. Proceedings. Waterloo: Open Publishing Association (OPA). 166--176 (2012; Zbl 1459.68132)]. The proofs mainly follow from careful and elementary considerations; though in some places they are based on the output of a computer calculation (provided in the appendix).
- Cellular automata and groups
- Closed Systems of Invertible Maps
- Computing by temporal order: asynchronous cellular automata
- Dynamics groups of asynchronous cellular automata
- Solution of Two Conjectures in Symbolic Dynamics
- Statistical mechanics of cellular automata
- Strongly universal reversible gate sets
- The classification of reversible bit operations
- The group of reversible Turing machines
- Towards an algebraic theory of Boolean circuits.
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)
