𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A computation-universal two-dimensional 8-state triangular reversible cellular automaton

✍ Scribed by Katsunobu Imai; Kenichi Morita


Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
731 KB
Volume
231
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis


A reversible cellular automaton (RCA) is a cellular automaton (CA) whose global function is injective and every conÿguration has at most one predecessor. Margolus showed that there is a computation-universal two-dimensional 2-state RCA. But his RCA has a non-uniform neighbor, so Morita and Ueno proposed 16-state computation-universal RCA using partitioned cellular automata (PCA). Because PCA can be regarded as a subclass of standard CA, their models have a standard neighbor. In this paper, we show that the number of states of Morita and Ueno's models can be reduced. To decrease the number of states from their models with preserving isotropic and bit-preserving properties, we used a triangular 3-neighbor, and thus an 8-state RCA can be possible. This is the smallest state two-dimensional RCA under the condition of isotropic property in the framework of PCA. We show that our model can simulate basic circuit elements such as unit wires, delay elements, crossing wires, switch gates and inverse switch gates, and it is possible to construct a Fredkin gate by combining these elements. Since Fredkin gate is known to be a universal logic gate, our model has computation-universality.


📜 SIMILAR VOLUMES