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

• Autorzy: Xu Wen-Li , Lee Jia , Chen Hui-Hui , Isokawa Teijiro

Identyfikatory

DOI

10.3233/FI-2019-1779

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

asynchronous circuit; cellular automaton; number base conversion; random fluctuation; universal computation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 165, nr 2
• Strony: 139--156
• Opis fizyczny: Bibliogr. 22 poz., rys., tab.

Twórcy

autor

Xu Wen-Li

• College of Computer Science, Chongqing University, Chongqing, China

autor

Lee Jia

• College of Computer Science, Chongqing University, Chongqing, China

autor

Chen Hui-Hui

• College of Computer Science, Chongqing University, Chongqing, China

autor

Isokawa Teijiro

• Graduate School of Engineering, University of Hyogo, Himeji, Japan

Bibliografia

• [1] Adachi S, Lee J, Peper F. On signals in asynchronous cellular spaces, IEICE Trans. Inform. Systems 2004;E87-D(3):657-668.
• [2] Bandyopadhyay A, Pati R, Sahu S, Peper F, Fujita D. Massively parallel computing on an organic molecular layer, Nature Physics 2010;6:369-375. doi:10.1038/nphys1636.
• [3] Banks ER. Universality in cellular automata, IEEE 11th Ann. Symp. on Switching and Automata Theory, CA, 1970. URL http://doi.ieeecomputersociety.org/10.1109/SWAT.1970.27.
• [4] Bennett C. The thermodynamics of computation—a review, Int. J. Theor. Phys. 1982;21(12):905-940. doi:10.1007/BF02084158.
• [5] Dasmahapatra S, Werner J, Zauner KP¿ Noise as a computational resource, Int. J. Unconventional Comput. 2006;2(4):305-319. URL https://eprints.soton.ac.uk/id/eprint/263230.
• [6] Hauck S. Asynchronous design methodologies: an overview, Proc. IEEE 1995;83(1):69-93. doi:10.1109/5.362752.
• [7] Keller RM. Towards a theory of universal speed-independent modules, IEEE Trans. Comput. 1974;C-23(1):21-33. doi:10.1109/T-C.1974.223773.
• [8] Lee J, Adachi S, Peper F, Morita K. Embedding universal delay-insensitive circuits in asynchronous cellular spaces, Fund. Inform. 2003;58(3-4):295-320.
• [9] Lee J, Peper F, Adachi S, Morita K. Universal delay-insensitive circuits with bi-directional and buffering lines, IEEE Trans. Comput. 2004;53(8):1034-1046. doi:10.1109/TC.2004.51.
• [10] Lee J. A simple model of asynchronous cellular automata exploiting fluctuation, J. Cellular Automata 2011;6(4-5):341-352.
• [11] Lee J, Peper F, Leibnitz K, Gu P. Characterization of random fluctuation-based computation in cellular automata, Inf. Sci. 2016;352-353:150-166. URL https://doi.org/10.1016/j.ins.2016.02.046.
• [12] Lee J, Peper F, Naruse M, Ohtsu M, Kawazoe T, Cotofana SD, Takahashi Y, Kish LB, Kubota T. Brownian circuits: Designs, Int. J. Unconventional Computing 2016;12:341-362.
• [13] Lee J, et al. Supplementary material to this paper: video entitled “DIconverter.mp4”.
• [14] Mano MM, Kime CR, Martin T. Logic and Computer Design Fundamentals, 5th Edition, Pearson, 2016. ISBN-10:0133760634, 13:978-0133760637.
• [15] Murata T. Petri Nets: Properties, analysis and applications, Proc. IEEE 1989;77(4):541-580. doi:10.1109/5.24143.
• [16] Patra P, Fussell DS. Conservative delay-insensitive circuits, Workshop on Physics and Computation, 1996 pp. 248-259.
• [17] Peper F, Lee J, Adachi S, Mashiko S. Laying out circuits on asynchronous cellular arrays: a step towards feasible nanocomputers? Nanotechnology 2003;14(4):469-485. URL http://stacks.iop.org/0957-4484/14/i=4/a=312.
• [18] Peper F, Lee J, Isokawa T. Brownian cellular automata, J. Cellular Automata 2010;5(3):185-206. URL https://dblp.org/rec/bib/journals/jca/PeperLI10.
• [19] Peper F, Lee J, Carmona J, Cortadella J, Morita K. Brownian Circuits: Fundamentals. ACM Journal on Emerging Technologies in Computing Systems 2012;9(1):Article 3. doi:10.1145/2422094.2422097.
• [20] Schneider O, Worsch T. A 3-state asynchronous CA for the simulation of delay-insensitive circuits, Proc. ACRI 2012, vol. 7495 of LNCS, 2012:565-574. doi:10.1007/978-3-642-33350-7_58.
• [21] Schönfisch B, de Roos A. Synchronous and asynchronous updating in cellular automata, BioSystems 1999;51(3):123-143. doi:10.1016/S0303-2647(99)00025-8.
• [22] Steward WJ. Probability, Markov Chains, Queues, and Simulation, Princeton University Press, 2009. ISBN-9780691140629.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).