A universal Brownian cellular automaton with 3 states and 2 rules
Tóm tắt
This paper presents a 3-state asynchronous cellular automaton (CA) that requires merely two transition rules to achieve computational universality. This universality is achieved by implementing Priese’s delay-insensitive circuit elements, called the E-element and the K-element, on the cell space of a so-called Brownian CA, which is an asynchronous CA containing local configurations that conduct a random walk in the circuit topology.
Tài liệu tham khảo
Biafore M (1994) Cellular automata for nanometer-scale computation. Physica D 70:415–433
Dasmahapatra S, Werner J, Zauner KP (2006) Noise as a computational resource. Int J Unconv Comput 2(4):305–319
Durbeck LJK, Macias NJ (2001) The cell matrix: an architecture for nanocomputing. Nanotechnology 12:217–230
Isokawa T, Peper F, Ono K, Matsui N (2016) On a universal brownian cellular automata with 3 states and 2 rules. In: Proceedings of the 12th international conference on cellular automata for research and industry (ACRI2016), pp 14–23 . LNCS9863
Kish LB (2006) Thermal noise driven computing. Appl Phys Lett 89(14):144,104–1–3
Lee J, Peper F (2008) On Brownian cellular automata. In: Proceedings of AUTOMATA 2008, Luniver Press, pp 278–291
Lee J, Peper F (2009) Efficient computation in brownian cellular automata. In: Proceedings of of 4th international workshop on natural computing, pp 47–56
Lee J, Peper F, Cotofana S, Naruse M, Ohtsu M, Kawazoe T, Takahashi Y, Shimokawa T, Kish L, Kubota T (2016) Brownian circuits: designs. Int J Unconv Comput 12(5–6):341–362
Lee J, Peper F, Leibnitzc K, Gu P (2016) Characterization of random fluctuation-based computation in cellular automata. Inf Sci 252–253:150–166
Peper F, Lee J, Adachi S, Mashiko S (2003) Laying out circuits on asynchronous cellular arrays: a step towards feasible nanocomputers? Nanotechnology 14:469–485
Peper F, Lee J, Carmona J, Cortadella J, Morita K (2013) Brownian circuits: fundamentals. ACM J Emerg Technol Comput Syst 9(1), 3:1–24
Peper F, Lee J, Isokawa T (2009) Cellular nanocomputers: a focused review. Int J Nanotechnol Mol Comput 1:33–49
Peper F, Watanabe T, Isokawa T, Matsui N (2014) Cellular automaton-based nanoelectronic hardware. In: Proceedings of the 6th IEEE international nanoelectronics conference (IEEE INEC 2014), pp 1–3
Priese L (1983) Automata and concurrency. Theor Comput Sci 25(3):221–265
Yanagida T, Ueda M, Murata T, Esaki S, Ishii Y (2007) Brownian motion, fluctuation and life. Biosystems 88(3):228–242