Logic Gates Formed by Perturbations in an Asynchronous Game of Life

Abstract

The game of life (GL), a type of two-dimensional cellular automaton, has been the subject of many studies because of its simple mechanism and complex behavior. In particular, the construction of logic circuits using the GL has helped to extend the concept of computation. Conventional logic circuits assume deterministic transitions due to the synchronicity of the classic GL. However, they are fragile to noise and cannot maintain the expected behavior in an environment with noise. In this study, a probabilistic logic gate model was constructed using perturbations in an asynchronous game of life (AGL). Since our asynchronous automaton had no heterogeneity in either the horizontal or vertical directions, it was symmetrical with respect to spatial structure. On the other hand, the construction of the logical gate was implemented to contain heterogeneity in the horizontal or vertical directions, which could allow an AND gate and an OR gate in a single system. It was based on the phase transition between connected and unconnected phases, which is newly discovered in this study. In the model, perturbations symmetrically entail operations successful and unsuccessful, and this symmetrical double action is given not to interfere with established operations but to make operations possible. Therefore, this model had a different meaning from logic gates that exclude perturbations or use them externally. The idea of this perturbation is analogous to the inherent noise that destroys and generates structures in biological swarms.

Keywords

• cellular automata
• asynchronous updating
• perturbations
• logic gate
• phase transition