See more in Publications and Presentations, Complex Systems Publications and Presentations

Sugata Mitra, Sujai Kumar (2006, Volume 16, Issue 3). Fractal Replication in Time Manipulated One-Dimensional Cellular Automata. Complex Systems. [Download draft pdf].

Abstract

Properties of elementary one dimensional cellular automata (CAs) have been studied extensively in the past by varying the number of states each cell can take, the neighborhood of the cell, or the transition rules by which each cell is updated. This paper describes a previously untried variation on a CA system, where each cell is able to anticipate its state one step in the future, and the entire system is allowed to revisit the past over many iterations. Manipulating the time domain in this way allows the CA to exhibit complex fractal replication behavior. Any configuration of active cells can be replicated endlessly while remaining constrained in a self-similar layout.

Index Terms

Cellular Automata, fractals, self-organizing systems

References

[1] E. F. Codd, Cellular Automata. Academic Press, 1968.
[2] J. von Neumann, “Theory of Self-Reproducing Automata,” in Essays on Cellular Automata, A. W. Burks, Ed. Univ. of Illinois Press, 1970.
[3] S. Wolfram, A New Kind of Science. Champaign, IL: Wolfram Media, 2002.
[4] P. Sarkar. “A brief history of cellular automata,” ACM Computing Surveys, vol. 32, no. 1, pp. 80-107, March 2000.
[5] M. Delorme. “An Introduction to Cellular Automata,” in Cellular Automata: A Parallel Model, M. Delorme and J. Mazoyer, Eds. Kluwer, 1998.
[6] E. Fredkin, “Digital mechanics: An informational process based on reversible universal CA,” Physica D, vol. 45, pp. 254-270, September 1990.
[7] S. J. Willson, “Cellular automata can generate fractals,” Discrete Applied Mathematics, vol. 8, pp. 91-99, 1984.
[8] M. Wójtowicz (2001, September 15). Cellular Automata rules lexicon [Online]. Available: http://www.mirwoj.opus.chelm.pl/ca/rullex_vote.html
[9] S. Wolfram, “Statistical Mechanics of Cellular Automata,” Reviews of Modern Physics, vol. 55, pp. 601-644, July 1983.
[10] M. Gardner. Wheels, Life and other Mathematical Amusements. W. H. Freeman, 1983.
[11] S. Kumar (2005, March), 2-CA Fractal Replicators [Online]. Available: http://ylog.org/complex/replicators.html