IJUC Home • Issue Contents

Logic Gates with Potential Output in an Asynchronous Game of Life
Yoshihiko Ohzawa and Yukio-Pegio Gunji

The game of life, a simple two-dimensional cellular automaton, has been widely studied because of its computational properties. Several models of logic gates have been proposed using the game of life. In most of them, the behavior is deterministic because the state of the cells is updated synchronously. Here, we propose a flexible logic gate model that allows for sequential changes in inputs by asynchronous updating. Probabilistic AND and OR gates are implemented by using the asynchronous rates as the inputs. These gates recover the correct output if the inputs are changed over time. The same mechanism can be applied to construct the RS flipflop. These results reveal that the output of our model is potentially nondeterministic due to asynchronous updating. While that situation is similar to the situation implemented by quantum automata, our model works with asynchronous updating instead of quantum states.

Keywords: Cellular automata, game of life, asynchronous updating, logic gates, sequential circuit, phase transition

Full Text (IP)