A Simple Model of Asynchronous Cellular Automata Exploiting Fluctuation
Jia Lee
Asynchronous cellular automata (ACAs) allow cells to undergo state transitions independently at random times. Computation in ACAs usually requires some special mechanism to control the unpredictable transitions of cells, which in turn causes the increase in the complexity of ACAs as compared to their synchronous counterpart. Nevertheless, inclusion of fluctuation into ACAs promises models with less complexity, e.g., the Brownian cellular automaton (Lee and Peper, 2008) which uses three cell states and three kinds of transition rules to conduct universal computation. By taking this approach one step further, we propose a novel cellular automaton in which local configurations representing signals will propagate randomly in the cellular space, as if they were subject to Brownian motion. Depending on merely two cell states and two kinds of transition rules, our new ACA can be used to construct any arbitrary asynchronous circuit in the cellular space, and hence, it is computationally universal. The reduced complexity of the new ACA may offer possibility of simple physical realizations.
Keywords: cellular automaton, Brownian motion, computational complexity, universal computation, asynchronous circuit