Abstract
Computation- and construction-universality in cellular automata (CA), first studied by von Neumann, has attracted steady research efforts, over the years, most employing synchronous CA. Asynchronous cellular automata (ACA), though of interest as most interactions in nature are asynchronous, have not been used for this task, other than by the indirect way of simulating a synchronous CA. In this paper, we propose a universal constructor on a self-timed cellular automaton (STCA), a particular type of ACA, in which cells are divided in four partitions, each with four states.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
von Neumann, J.: Theory of Self-Reproducing Automata. University of Illinois Press, Urbana (1966)
Codd, E.F.: Cellular Automata. Academic Press, New York (1968)
Banks, E.R.: Universality in cellular automata. In: IEEE 11th Ann. Symp. on Switching and Automata Theory, pp. 194–215 (1970)
Serizawa, T.: Three-state Neumann neighbor cellular automata capable of constructing self-reproducing machines. Syst. and Comput. in Japan 18, 33–40 (1987)
Priese, L.: On a simple combinatorial structure sufficient for sublying nontrivial self-reproduction. Journal of Cybernetics 6, 101–137 (1976)
Nehaniv, C.L.: Self-reproduction in asynchronous cellular automata. In: Proc. NASA/DoD Conf. on Evolvable Hardware, pp. 201–209 (2002)
Nakamura, K.: Asynchronous cellular automata and their computational ability. Systems, Computers, Controls 5, 58–66 (1974)
Lee, J., Adachi, S., Peper, F., Morita, K.: Embedding universal delay-insensitive circuits in asynchronous cellular spaces. Fundamenta Informaticae 58, 295–320 (2003)
Adachi, S., Peper, F., Lee, J.: Computation by asynchronously updating cellular automata. Journal of Statistical Physics 114, 261–289 (2004)
Peper, F., Lee, J., Adachi, S., Mashiko, S.: Laying out circuits on asynchronous cellular arrays: a step towards feasible nanocomputers? Nanotechnology 14, 469–485 (2003)
Hauck, S.: Asynchronous design methodologies: An overview. Proc. IEEE 83, 69–93 (1995)
Peper, F., Isokawa, T., Kouda, N., Matsui, N.: Self-timed cellular automata and their computational ability. Future Generation Computer Systems 18, 893–904 (2002)
Morita, K.: A simple universal logic element and cellular automata for reversible computing. In: Margenstern, M., Rogozhin, Y. (eds.) MCU 2001. LNCS, vol. 2055, pp. 102–113. Springer, Heidelberg (2001)
Takada, Y., Isokawa, T., Peper, F., Matsui, N.: Universal construction and selfreproduction on self-timed cellular automata (2004) (in Preparation)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Takada, Y., Isokawa, T., Peper, F., Matsui, N. (2004). Universal Construction on Self-Timed Cellular Automata. In: Sloot, P.M.A., Chopard, B., Hoekstra, A.G. (eds) Cellular Automata. ACRI 2004. Lecture Notes in Computer Science, vol 3305. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30479-1_3
Download citation
DOI: https://doi.org/10.1007/978-3-540-30479-1_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23596-5
Online ISBN: 978-3-540-30479-1
eBook Packages: Springer Book Archive