Brownian Cellular Automata
Ferdinand Peper, Jia Lee and Teijiro Isokawa
Brownian Cellular Automata are Cellular Automata (CA) in which certain configurations—like signals—fluctuate in the cell space in random semi-controlled ways. We present two models in this framework, both based on a Self-Timed Cellular Automaton (STCA), which is a kind of asynchronous CA. The first model is aimed at computation. It uses five transition rules to achieve computational universality, which is one rule less than in previous STCA-based models that allow parallel signals and arbitration between processes. Key to the model’s operation is the exploitation of random fluctuations to search for solutions in computational state space. The inherently slow random search process is sped up by the selective placement of so-called ratchets, which limit search to certain domains. The second Brownian CA model is aimed at the detection and isolation of defective cells in an online manner, i.e., while computation takes place. This model uses configurations moving around randomly in the cell space that stick to configurations of a static nature, i.e., to those configurations of which computations are blocked due to defects. Both models illustrate that random fluctuations can be exploited in CA to accomplish certain goals at the expense of only limited resources.
Keywords: Asynchronous CA, Brownian motion, Delay-insensitive circuits