کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
392226 | 664751 | 2016 | 17 صفحه PDF | دانلود رایگان |
A Brownian Cellular Automaton (BCA) is an Asynchronous Cellular Automaton (ACA) in which the timing of the local cell state transitions approaches a Poisson point process, and the global transitions between cell configurations can be formulated as an irreducible and reversible Markov chain. BCAs exploit fluctuations to find solutions of a computation via a stochastic search process. This characteristic has been shown to contribute to a decreased complexity of BCAs (Lee and Peper, 2008), as compared to non-Brownian ACAs with equivalent functionality. This paper proposes a computationally universal BCA that is based on a conventional ACA, rather than the previously employed block cellular automata, which have transition rules that update each cell simultaneously with its neighboring cells. The proposed allows for a more natural update model, in which no need arises to locally synchronize the cells in a neighborhood. The resulting BCA is significantly less complex than equivalent non-block non-Brownian ACAs, which demonstrates that random fluctuations can serve as a powerful resource for efficient computation on cellular automata.
Journal: Information Sciences - Volumes 352–353, 20 July 2016, Pages 150–166