A class of discrete dynamical systems with properties of both cellular automata and L-systems
- PDF / 1,646,548 Bytes
- 33 Pages / 595.276 x 790.866 pts Page_size
- 52 Downloads / 158 Views
(0123456789().,-volV)(0123456789(). ,- volV)
A class of discrete dynamical systems with properties of both cellular automata and L-systems Roderick Edwards1
•
Aude Maignan2
Springer Nature B.V. 2019
Abstract We introduce and explore a type of discrete dynamic system inheriting some properties of both cellular automata (CA) and L-systems. Originally suggested by Jean Della Dora, and thus called DEM-systems after him and the two current authors, these systems can have the structural flexibility of an L-system as well as algebraic properties of CA. They are defined as sequences on a one-dimensional loop with rules governing dynamics in which new sites can be created, depending on the states of a neighbourhood of sites, and complex behaviour can be generated. Although the definition of DEM-systems is quite broad, we define some subclasses, for which more complete results can be obtained. For example, we define an additive subclass, for which algebraic results on asymptotic growth are possible, and an elementary class of particularly simple rules, for which nevertheless impressive complexity is achievable. Unlike for CA, finite initial sequences can produce positive spatial entropy over time. However, even in cases where the entropy is zero, considerable complexity is possible, especially when the sequence length grows to infinity, and we demonstrate and study behaviours of DEM-systems including fragmentation of sequences, self-reproducing patterns, self-similar but irregular patterns, patterns that not only produce new sites but produce producers of new sites, and sequences whose growth rate is sublinear, linear, quadratic, cubic, or exponential. The most complex behaviour from small finite initial conditions and the simplest class of rules appear to have positive entropy, a suggestion for which we have so far only stong numerical evidence, though we present a proof for these ‘elementary’ DEM-systems that entropy cannot reach the theoretical maximum of 1. Keywords Complexity Entropy Self-reproducing systems Self-organizing systems Cellular automata L-systems Mathematics Subject Classification 68Q80 68Q70 68Q30 68Q19
1 Introduction Tao produced the One. The One produced the two. The two produced the three. And the three produced the ten thousand things. & Roderick Edwards [email protected] Aude Maignan [email protected] 1
Department of Mathematics and Statistics, University of Victoria, PO Box 1700 STN CSC, Victoria, BC V8W 2Y2, Canada
2
Univ. Grenoble Alpes, LJK, 51 rue des Mathematiques, B. P. 53, 38041 Grenoble Cedex 9, France
- from Tao Te Ching (Wing-Tsit Chan, trans., Prentice-Hall, 1963) Dynamical systems are usually studied in the context of a fixed state space or phase space. However, some phenomena are more naturally described by systems for which the state space itself evolves over time: for example, the growth of filament segments in Anabaena catenula (Prusinkiewicz and Lindenmayer 1996), neural networks that grow in ontogenetic or phylogenetic time (Bohun et al. 20
Data Loading...
