No Access

UNIVERSAL CONSTRUCTION AND SELF-REPRODUCTION ON SELF-TIMED CELLULAR AUTOMATA

YOUSUKE TAKADA

Division of Computer Engineering, University of Hyogo, 2167 Shosha, Himeji, Hyogo, 671-2201, Japan

Present address: Canopus Co., Ltd., 1-2-2 Murotani, Nishi-ku, Kobe, Hyogo, 651-2241, Japan.

Search for more papers by this author

TEIJIRO ISOKAWA

Division of Computer Engineering, University of Hyogo, 2167 Shosha, Himeji, Hyogo, 671-2201, Japan

Corresponding author.

Search for more papers by this author

FERDINAND PEPER

Nanotechnology Group, National Institute of Information and Communications Technology, 588-2 Iwaoka, Iwaoka-cho, Nishi-ku, Kobe, 651-2492, Japan

Search for more papers by this author

, and

NOBUYUKI MATSUI

Division of Computer Engineering, University of Hyogo, 2167 Shosha, Himeji, Hyogo, 671-2201, Japan

Search for more papers by this author

https://doi.org/10.1142/S0129183106009497Cited by:11 (Source: Crossref)

Abstract

This paper proposes a universal constructor implemented on a self-timed cellular automaton, which is a particular type of asynchronous cellular automaton. Our construction utilizes the asynchronous nature of the underlying cellular automaton in a direct way, as a result of which it is simpler than the conventional construction based on the simulation of a synchronous cellular automaton by an asynchronous cellular automaton. Our model employs 39 rotation-invariant rules and the state of each cell is encoded by 8 bits.

This is an extended version of the paper entitled "Universal Construction on Self-Timed Cellular Automata" presented at the Sixth International Conference on Cellular Automata for Research and Industry (ACRI) in Amsterdam on 25–27 October 2004.

Keywords:

You currently do not have access to the full text article.
Recommend the journal to your library today!

References

J. von Neumann , Theory of Self-Reproducing Automata ( University of Illinois Press , 1966 ) . Google Scholar
E. F. Codd , Cellular Automata ( Academic Press , New York , 1968 ) . Google Scholar
E. R. Banks, IEEE 11th Ann. Symp. on Switching and Automata Theory (1970) pp. 194–215. Google Scholar
T. Serizawa, Syst. and Comput. Japan 18, 33 (1987). Crossref, Google Scholar
5. R. Nobili and U. Pesavento, Artificial Worlds and Urban Studies (1996). The modified version entitled "John von Neumann's Automata Revisited" is available at http://www.pd.infn.it/%7Ernobili/pdf_files/jvnconstr.pdf. . Google Scholar
U. Pesavento, Artificial Life 2, 337 (1995). Crossref, Google Scholar
T. Hutton, http://www.sq3.org.uk/Evolution/JvN/ . Google Scholar
C. G. Langton, Physica D 10, 135 (1984), DOI: 10.1016/0167-2789(84)90256-2. Crossref, Web of Science, ADS, Google Scholar
J. A. Reggiaet al., Science 259, 1282 (1993). Crossref, Web of Science, ADS, Google Scholar
K. Morita and K. Imai, Theoret. Comput. Sci. 168, 337 (1996). Crossref, Web of Science, Google Scholar
L. Priese, J. Cybernetics 6, 101 (1976). Crossref, Web of Science, Google Scholar
C. L. Nehaniv, Proc. NASA/DoD Conf. on Evolvable Hardware (2002) pp. 201–209. Google Scholar
K. Nakamura, Systems, Computers, Controls 5, 58 (1974). Google Scholar
J. Leeet al., Fund. Inform. 58, 295 (2003). Web of Science, Google Scholar
S. Adachi, F. Peper and J. Lee, J. Statistical Phys. 114, 261 (2004), DOI: 10.1023/B:JOSS.0000003112.54283.ac. Crossref, Web of Science, ADS, Google Scholar
F. Peperet al., Nanotechnology 14, 469 (2003), DOI: 10.1088/0957-4484/14/4/312. Crossref, Web of Science, ADS, Google Scholar
F. Peperet al., Future Generation Comput. Syst. 18, 893 (2002). Crossref, Web of Science, Google Scholar
J. Villasenor and W. H. Mangione-Smith, Scientific American 66 (1997). Google Scholar
A. DeHon, IEEE Comput. 33, 41 (2000). Crossref, Web of Science, Google Scholar
K. Morita, Machines, Computations, and Universality (Springer, 2001) pp. 102–113. Crossref, Google Scholar
S. Hauck, Proc. IEEE 83, 69 (1995), DOI: 10.1109/5.362752. Crossref, Web of Science, Google Scholar
J. Leeet al., Unconventional Models of Computation (Springer, 2002) pp. 220–229. Crossref, Google Scholar
M. L. Minsky , Computation: Finite and Infinite Machines ( Prentice-Hall , 1967 ) . Google Scholar