×
Takada, Yousuke; Isokawa, Teijiro; Peper, Ferdinand; Matsui, Nobuyuki

Asynchronous self-reproducing loops with arbitration capability. (English) Zbl 1111.68080

Physica D 227, No. 1, 26-35 (2007).
Summary: This paper proposes Self-Reproducing Loops (SRLs) implemented on a self-timed cellular automaton, a type of asynchronous cellular automaton. Self-reproduction of a wide variety of shapes of SRLs is made possible by employing the so-called shape-encoding mechanism, which self-inspects a loop and generates construction signals accordingly. Due to the model’s asynchronous mode of timing, a dynamic interplay between SRLs occurs, in which SRLs compete for space to place their offspring. Deadlock situations caused by the collisions are reliably arbitrated utilizing only local interactions of SRLs.

Cited in 2 Documents

MSC:

68Q80 Cellular automata (computational aspects)

Keywords:

self-reproduction; arbitration; self-timed cellular automata; asynchronous
Cite Review PDF
Full Text: DOI

References:

[1] von Neumann, J., Theory of Self-Reproducing Automata (1966), University of Illinois Press, Edited and completed by A.W. Burks
[2] (Burks, A. W., Essays on Cellular Automata (1970), University of Illinois Press) · Zbl 0228.94013
[3] Codd, E. F., Cellular Automata (1968), Academic Press: Academic Press New York · Zbl 0213.18301
[4] E.R. Banks, Universality in cellular automata, in: IEEE 11th Ann. Symp. on Switching and Automata Theory, 1970, pp. 194-215; E.R. Banks, Universality in cellular automata, in: IEEE 11th Ann. Symp. on Switching and Automata Theory, 1970, pp. 194-215
[5] Serizawa, T., Three-state Neumann neighbor cellular automata capable of constructing self-reproducing machines, Syst. Comput. Japan, 18, 4, 33-40 (1987)
[6] Nobili, R.; Pesavento, U., Generalized von Neumann’s automata I: A revisitation, (Artificial Worlds and Urban Studies (1996)), The modified version entitled “John von Neumann’s Automata Revisited” is available at
[7] Pesavento, U., An implementation of von Neumann’s self-reproducing machine, Artif. Life, 2, 4, 337-354 (1995)
[8] Langton, C. G., Self-reproduction in cellular automata, Physica D, 10, 135-144 (1984) · Zbl 0563.68048
[9] Reggia, J. A.; Armentrout, S. L.; Chou, H.-H.; Peng, Y., Simple systems that exhibit self-directed replication, Science, 259, 5099, 1282-1287 (1993) · Zbl 1226.68046
[10] Ibáñez, J.; Anabitarte, D.; Azpeitia, I.; Barrera, O.; Barrutieta, A.; Blanco, H.; Echarte, F., Self-inspection based reproduction in cellular automata, (Advances in Artificial Life, Third European Conference on Artificial Life. Advances in Artificial Life, Third European Conference on Artificial Life, ECAL95. Advances in Artificial Life, Third European Conference on Artificial Life. Advances in Artificial Life, Third European Conference on Artificial Life, ECAL95, LNCS, vol. 929 (1995)), 564-576
[11] Morita, K.; Imai, K., A simple self-reproducing cellular automaton with shape-encoding mechanism, (Artificial Life V: Proceedings of the Fifth International Workshop on the Synthesis and Simulation of Living Systems (1996), MIT Press), 489-496
[12] Morita, K.; Imai, K., Self-reproduction in a reversible cellular space, Theoret. Comput. Sci., 168, 337-366 (1996) · Zbl 0874.68221
[13] Sayama, H., A new structurally dissolvable self-reproducing loop evolving in a simple cellular automata space, Artif. Life, 5, 343-365 (1999)
[14] Mange, D.; Stauffer, A.; Petraglio, E.; Tempesti, G., Self-replicating loop with universal construction, Physica D, 191, 178-192 (2004) · Zbl 1077.68712
[15] Tomita, K.; Kurokawa, H.; Murata, S., Graph automata: Natural expression of self-reproduction, Physica D, 171, 4, 197-210 (2002) · Zbl 1008.37007
[16] Sipper, M., Fifty years of research on self-replication: An overview, Artif. Life, 4, 3, 237-257 (1998)
[17] Lohn, J. D., Cellular space models of self-replicating structures, (Mathematical and Computational Biology: Computational Morphogenesis, Hierarchical Complexity, and Digital Evolution (1999)), 11-30 · Zbl 0933.92002
[18] Salzberg, C.; Sayama, H., Heredity, complexity, and surprise: Embedded self-replication and evolution in CA, (6th International Conference on Cellular Automata for Research and Industry. 6th International Conference on Cellular Automata for Research and Industry, ACRI 2004. 6th International Conference on Cellular Automata for Research and Industry. 6th International Conference on Cellular Automata for Research and Industry, ACRI 2004, LNCS, vol. 3305 (2004)), 161-171 · Zbl 1116.68527
[19] McMullin, B., John von Neumann and the evolutionary growth of complexity: Looking backwards, looking forwards..., Artif. Life, 6, 347-361 (2000)
[20] Peper, F.; Lee, J.; Adachi, S.; Mashiko, S., Laying out circuits on asynchronous cellular arrays: A step towards feasible nanocomputers?, Nanotechnology, 14, 4, 469-485 (2003)
[21] Takada, Y.; Isokawa, T.; Peper, F.; Matsui, N., Construction universality in purely asynchronous cellular automata, J. Comput. Syst. Sci., 72, 1368-1385 (2006) · Zbl 1119.68122
[22] Takada, Y.; Isokawa, T.; Peper, F.; Matsui, N., Universal construction and self-reproduction on self-timed cellular automata, Internat. J. Modern Phys. C, 17, 985-1007 (2006) · Zbl 1110.68081
[23] P. Gács, Deterministic computations whose history is independent of the order of asynchronous updating, Tech. Rep., Computer Science Dept., Boston Univ., 1997; P. Gács, Deterministic computations whose history is independent of the order of asynchronous updating, Tech. Rep., Computer Science Dept., Boston Univ., 1997
[24] Nakamura, K., Asynchronous cellular automata and their computational ability, Syst. Comput. Contr., 5, 5, 58-66 (1974)
[25] C.L. Nehaniv, Self-reproduction in asynchronous cellular automata, in: Proc. NASA/DoD Conf. on Evolvable Hardware, 2002, pp. 201-209; C.L. Nehaniv, Self-reproduction in asynchronous cellular automata, in: Proc. NASA/DoD Conf. on Evolvable Hardware, 2002, pp. 201-209
[26] Toffoli, T., Integration of the phase-difference relations in asynchronous sequential networks, (Ausiello, G.; Böhm, C., Proc. of the Fifth Colloquium on Automata, Languages, and Programming. Proc. of the Fifth Colloquium on Automata, Languages, and Programming, ICALP. Proc. of the Fifth Colloquium on Automata, Languages, and Programming. Proc. of the Fifth Colloquium on Automata, Languages, and Programming, ICALP, Lecture Notes in Computer Science, vol. 62 (1978), Springer), 457-463 · Zbl 0389.94027
[27] Lee, J.; Adachi, S.; Peper, F.; Morita, K., Asynchronous game of life, Physica D, 194, 369-384 (2004) · Zbl 1076.82031
[28] Peper, F.; Isokawa, T.; Kouda, N.; Matsui, N., Self-timed cellular automata and their computational ability, Future Gener. Comput. Syst., 18, 7, 893-904 (2002) · Zbl 1042.68080
[29] Lee, J.; Peper, F.; Adachi, S.; Morita, K., Universal delay-insensitive circuits with bi-directional and buffering lines, IEEE Trans. Comput., 53, 8, 1034-1046 (2004)
[30] Lee, J.; Peper, F.; Adachi, S.; Mashiko, S., Universal delay-insensitive systems with buffering lines, IEEE Trans. Circuits Syst., 52, 742-754 (2005) · Zbl 1374.94914
[31] Lee, J.; Adachi, S.; Peper, F., Reliable self-replicating machines in asynchronous cellular automata, (Proc. IEICE General Conference 2005, vol. D (2005))
[32] T. Isokawa, Self-adaptation in natural computing systems, Ph.D. Thesis, Himeji Institute of Technology, 2004; T. Isokawa, Self-adaptation in natural computing systems, Ph.D. Thesis, Himeji Institute of Technology, 2004
[33] Peper, F.; Lee, J.; Abo, F.; Isokawa, T.; Adachi, S.; Matsui, N.; Mashiko, S., Fault-tolerance in nanocomputers: A cellular array approach, IEEE Trans. Nanotechnol., 3, 1, 187-201 (2004)
[34] Lee, J.; Peper, F.; Adachi, S.; Morita, K.; Mashiko, S., Reversible computation in asynchronous cellular automata, (UMC. UMC, LNCS, vol. 2509 (2002)), 220-229 · Zbl 1029.68101
[35] Bonabeau, E.; Dorigo, M.; Theraulaz, G., Swarm Intelligence: From Natural to Artificial Systems (1999), Oxford University Press · Zbl 1003.68123
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.