Universal Computation in a Simplified Brownian Cellular Automaton with von Neumann Neighborhood

Abstract

A Brownian cellular automaton (BCA) is an asynchronous cellular automaton (ACA) in which local configurations representing signals may move forth and back randomly, as if they were undergoing random walks. The random fluctuation offers a natural mechanism to propagate signals in the 2-dimensional cell space, and to cross signals moving in directions perpendicular to each other. As a result, the BCA in (Lee et al., 2016) employs 4 cell states and 17 transition rules to conduct universal computation, both of which are less than other equivalent ACAs in the literature. This paper aims to advance the fluctuation-based scheme one step further, via proposing a new BCA with 4 states and 14 rules that achieves a reduction in the number of transition rules. We show that the BCA is capable of implementing any arbitrary logic circuit, thereby proving its universality in computation. We illustrate this by implementing a circuit that converts a 4-bit number to its equivalent hexadecimal digit.