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

Article type: Research Article

Authors: Xu, Wen-Li^a | Lee, Jia^{a; *} | Chen, Hui-Hui^a | Isokawa, Teijiro^b

Correspondence: [*] Address for correspondence: Shazhengjie 174, Shapingba, Chongqing 400044, China. Also works: Chongqing Key Laboratory of Software Theory & Technology, Chongqing, China.

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.

Keywords: cellular automaton, asynchronous circuit, universal computation, number base conversion, random fluctuation

DOI: 10.3233/FI-2019-1779

Journal: Fundamenta Informaticae, vol. 165, no. 2, pp. 139-156, 2019