On Brownian cellular automata

Jia Lee1 and Ferdinand Peper2,3
1 Celartem Technology Inc., Tokyo, Japan
2 National Institute of Information and Communications Technology,
Nano ICT Group, Kobe, Japan
3 University of Hyogo, Division of Computer Engineering, Himeji, Japan

Abstract
Brownian Cellular Automata are asynchronously timed models that allow certain configurations\like signals\to fluctuate in the cellspace over time in random semi-controlled ways.We present such a model and prove its computational universality by showing primitive configurations on the cell space from which computational structures can be constructed. The proposed model has 3-state cells, which are governed by three transition rules. Key to the modelfs operation is the exploitation of random fluctuations to search for solutions in computational state space.We show how to do this, and how to speed up the searching process such that it becomes competitive with traditional computation methods on CA. Future designs of computers based on devices with nanometer-scale feature sizes may require fluctuating behavior of signals, like in the proposed model, as an important ingredient to achieve efficient operation.

doi: