Frieze-Generation Using Artificial Life

Year: 2003 Authors: Dirk Fischer; Eric Goles; Mario Markus

Core claim

Simple periodic forcing of Langton’s ant produces a wide variety of complex frieze patterns with apparent infinite sensitivity to parameter changes.

Topics

Langton’s ant, frieze patterns, periodic forcing, complexity

Domains

cellular automata, dynamical systems, modular arithmetic, complexity theory, pattern generation, frieze design, visual art

Methods

periodic binary forcing, computer simulation, parameter perturbation, grid evolution

Media

square grid, binary sequence, computer-generated figures

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

ISAMA The International Society of the Arts, Mathematics, and Architecture BRIDGES Mathematical Connections in Art, Music, and Science

Frieze-Generation Using Artificial Life

Dirk Fischer${}^a$, Eric Goles${}^b$ and Mario Markus${}^a$

${}^a$ Max-Planck-Institut für molekulare Physiologie Postfach 500247, 44202 Dortmund, Germany e-mail: markus@mpi-dortmund.mpg.de

${}^b$ Centre for Mathematical Modelling, UMR 2071 CNRS-Universidad de Chile Casilla 170-3, Santiago, Chile e-mail: egoles@dim.uchile.cl

Abstract

We modify the behaviour of the virtual ant introduced by Langton [1] by forcing it with periodical binary sequences. The turning direction of the ant at the $i^{\text{th}}$ iteration depends on whether the $i^{\text{th}}$ element of the binary sequence is zero or one. An overwhelming variety of frieze-like trajectories is obtained. Thus, this system is a novel prototype of high complexity resulting from simple rules. If the forcing is described by a real-valued parameter $p$, then any computationally feasible change $\Delta p$ renders completely different patterns. Thus, sensitivity with respect to the control parameter can be conjectured to be infinitely large.

Introduction

A well-known cellular automaton model that has been used in artificial life research is Langton’s ant (see [1-7]). Its behaviour is defined on a two-dimensional square grid, as illustrated in Fig. 1a. The ant heads in one of four possible directions. If it enters a white square, it turns 90 degrees to the left and paints this square black. If it enters a black square, it turns 90 degrees to the right and paints this square white. Disordered patterns appear until 9977 iterations. Then, unexpectedly, the ant moves periodically in one of the four possible diagonal directions (as e.g. in the upper left of Fig. 1b). It has been rigorously shown [7] that the temporal period $\tau$ on this periodical pattern is $\tau =104$ steps.

It is instructive to point out that Langton’s ant can be considered as a very simple description of a physical particle in a scattering environment. In fact, in so-called Lorentz lattice gases appearing in statistical mechanics, scatterers can be assumed to be distributed on a lattice; a scatterer is changed after a particle interacts with it [8-10]. Langton’s ant would correspond - in a highly simplified model - to a particle that is scattered $90^{\circ }$ to the right or $90^{\circ }$ to the left, these directions being reversed (due to modification of the scatterer) after each scattering event. Related descriptions can be used for charged particles within inhomogeneous magnetic fields, e.g. in a turbulent magnetized plasma [8].

A number of studies [2, 5] have been devoted to a particular generalization of Langton’s algorithm. In this generalization, $n$ states $k=0,1,2,\dots ,n-1$ are considered, instead of just two states (black and white). After the ant leaves a cell in state $k$, this state changes to $k+1$ (modulo $n$). A rule-string (length $n$) of 0’s and 1’s is given. If $r_k$ is the $k^{\text{th}}$ bit of that string, then the ant turns to the right if $r_k=1$ and to the left if $r_k=0$. It could be shown that the ant’s track is

151

always unbounded, provided the rule-string contains at least one 1 and one 0 (see also [2, 5]). An interesting result of the generalization to $n$ states with $n\ge 3$ is the appearance of a large variety of complex patterns with bilateral symmetry [4, 5].

a)

Figure 1: Langton’s ant. a) Initial steps. b) Periodical pattern (upper left) following a transient disordered pattern (partially shown in the lower right).

In this contribution we present a different type of generalization. It consists in maintaining the number of states $n=2$, but introducing infinitely long periodical sequences $\{r_m\}$ of 0’s and 1’s, which are applied as follows; the $m^{\mathrm{th}}$ element of that sequence is considered at the $m^{\mathrm{th}}$ iteration $(m=0,1,2,\dots )$; if $r_m=0$, then the ant behaves as in Langton’s case (Fig. 1); if $r_m=1$, then the ant will turn to the left if it enters a black square and to the right if it enters a white square. As in Langton’s algorithm, the square will always change its colour after the ant turns by 90 degrees.

We shall consider two types of periodicities of the sequence $\{r_m\}$:

Forcing type A:

A string of $j$ 0’s is followed by a single 1, then by $j$ 0’s, and so on. (Example: for $j=3$, $r_m=000100010001\dots$).

Forcing type B:

The iteration

is performed. The $x_m$ and the parameter $p$ are real numbers in the interval [0,1]. We set $r_m=0$ if $0\le x_m\le 1/2$ and $r_m=1$ otherwise. $x_0$ is set to 0.2. Note that Langton’s ant corresponds to the case $p=0$. The intention behind this procedure is to study the sensitivity of the outcome in dependence of a continuous parameter ($p$ in our case), which can be subject to arbitrarily small perturbations.

152

Since calculations are performed with a finite number of digits, we can write $p$ as a rational number $p=N/D$. It is easy to show that the denominator $D$ is a period of the sequence $\{r_m\}$. In fact, Eq. (1) can be written as

$D$ is a period if and only if

Note that the smallest possible forcing period $T$ is given by the smallest possible denominator $D$ fulfilling Eq. (6), which appears if $N$ and $D$ are relatively prime. We will always let the ant start in a completely white array of cells, except in cases (exemplified in this report only in Fig. 3) in which we examine the effect on the ant’s track as it moves from a white into a black array.

Results

Figs. 2 through 4 illustrate the overwhelming variety of frieze-like patterns we obtained after the initial disordered transient. The patterns are shown here at different scales and are rotated differently, so that they are all displayed horizontally. The actual direction of the ant’s track or “frieze”, with respect to the x-axis is given by $\phi$ in Table 1. The height of the pictures after rotation (angle $\phi$) is given by $H$ in Table 1 (the unit is the length of the side of the square cells). Note that after rotation the contents of the cells are positioned on an horizontally aligned grid, so that $H$ is an integer. Table 1 also indicates the type of forcing (A or B, as described in the preceding paragraph), the parameters $p$ (for B) or $j$ (for A), the forcing period $T$, the temporal period $\tau$ of the frieze and the time $T_d$ of transient disorder before the ant’s track becomes periodical.

A transformation of the shape of the frieze by letting the ant move from a grid containing only white cells into a grid consisting only of black cells is illustrated in Fig. 3. The two rows for Fig. 3 in Table 1 correspond to the two periodical trajectories described by the ant, as shown in the figure. Depending on the forcing sequence and on the phase at which the ant reaches the black region, we also found reflection, diffraction, parallel displacement or disordering of the ant’s track.

The fact that $p$ can be varied continuously in Eq. (1) allowed to investigate the effect of very small changes in $p$. We found that the shape of the frieze changed considerably, no matter how small was the change in $p$. A first example is Fig. 2h, as compared to Fig. 2b, with $p$ differing by $3\cdot 10^{-5}$. Another example is Fig. 2v, as compared to Fig. 2b, the difference in $p$ being $10^{-5}$. Outcomes involving even smaller changes in $p$ are illustrated in Fig. 4. Fig. 4a and Fig. 4b were obtained by changing $p$ corresponding to Fig. 2b by $-5\cdot 10^{-6}$ and $5\cdot 10^{-6}$, respectively. Fig. 4c was obtained by changing $p$ corresponding to Fig. 2s by $2\cdot 10^{-6}$. Smaller changes of $p$ were not possible because they yielded so large denominators $T$ (recall $p=N/T$) that the track periods became prohibitively long for our computational facilities. Complications arising from long periods did occur, for example in the case of Fig. 2m ($T=10^7$); here, the track shown in the figure changed later on; however, we had to break off calculations due to our limited computational time; therefore we are not sure whether Fig. 2m is part of a longer periodical track or if it is a transient ($\phi$ and $H$ are given for the displayed fragment in this case).

Table 1: Forcing type (second column), parameter (third column) and features of the friezes shown in Figs. 2 through 4. The parameter $p$ corresponds to forcing type B; the parameter $j$ corresponds to forcing type A. Questionmarks indicate that the pattern may be a transient.

Conclusions and future work

The generalization of Langton’s ant presented in previous works ( $n\ge 3$ states and a rule-string of finite length $n$ ) yielded a large variety of symmetrical patterns during the transient phase before

giving way to a periodic pattern [3-5]. By contrast, the generalization presented here yielded a surprising variety of periodical patterns; moreover, these periodical patterns have a pleasing aesthetic appearance.

It is noteworthy that any small change in the value of the parameter $p$ - up to the constraints imposed by our computational resources - leads to a completely different periodic pattern. This result reminds us of dynamical systems with “riddled basins” [11, 12], which render different attractors for arbitrarily small changes of a control parameter. However, the unpredictability found in the present work is more drastic because for riddled basins the probability of attaining the same attractor increases as the parameter difference decreases, which is not the case here. Note, however, that for riddled basins different attractors can be obtained for arbitrarily small changes of control parameters as well as from initial conditions, while the ant’s tracks are mainly affected by changes of the control parameter.

The work presented here also brings to mind Joseph Marie Jacquard’s method (devised around 1800) to generate complicated periodical patterns in woven fabrics using punched cards. In fact, cards have holes (1’s) and no-holes (0’s). Charles Babbage and Lady Ada Lovelace (Lord Byron’s daughter, born 1815) used Jacquard’s principle to supply instructions for their engines and calculating programmes, which are considered as seminal in the history of computer science (see [13]). One should keep in mind that there is a direct correspondence of strings and patterns in Jacquard’s machines, while our ant walks back, deletes and remakes patterns so frequently (e.g. Fig.1a), so that there is no obvious correspondence between our binary strings and the complex emergent friezes (in particular, this can be seen in Fig. 3). Nowadays immense amounts of patterns can be generated on monitor screens by letting the computer scan possible strings; this allows a selection by the user comparable to that of a photographer who selects a contest-winning picture by walking through the world with his camera. It is a philosophical or semantic matter to decide if such a selection has to do with “creativity”. In any case, the massive automatic generation of novel patterns by the computer can lead to surprises and such surprises may well enrich a designer’s collection.

Note another interesting outcome of this work: the periodical forcing, as introduced in the present work, in some cases considerably reduces the number of transient steps occurring before a periodical track emerges. This is seen by comparing $T_d$ in Table 1 with the 9977 disordered transient steps of Langton’s ant. In one case we found the astonishing result $T_d=0$ (Fig. 2x), meaning that no disordered pattern occurs at all. In other cases, $T_d$ is highly increased, as compared to Langton’s ant; one example is $T_d=7528047$ (Fig. 2v).

For future work we propose to try other types of forcing, e.g.: i) T/2 1’s, T/2 0’s, T/2 1’s,…; or ii) interpreting a periodic sequence of 0’s and 1’s to mean: leave the color unchanged when 0 but change the color when 1.

We want to close with the remark that we are dealing here with a novel prototype of complex pattern formation resulting from extremely simple rules. This is the most dramatic difference to Jacquard’s mechanism, in which the complexities of the patterns and of the punched cards are comparable. In contrast, the emergence of complexity described in the present work is to be added to the list of amazing phenomena found in other cellular automata [14], in biological morphogenesis [15] or in Lyapunov diagrams [16-18].

Acknowledgements

Mario Markus thanks the Center for Mathematical Modeling (Santiago de Chile) for their hospitality and financial support. Also, we thank Karsten Kötter for most fruitful discussions.

155

156

References

[1] C. Langton, Studying artificial life with cellular automata, Physica D, Vol. 22, pp. 120-149. 1986.

[2] D. Gale, The industrious ant, Math. Intelligencer, Vol. 15, pp. 54-55. 1993.

[3] I. Stewart, The ultimate in anty-particles, Sci. Am., July, pp. 88-91. 1994.

[4] J. Propp, Further Ant-ics, Math. Intelligencer, Vol. 16, pp. 37-42. 1994.

[5] D. Gale, J. Propp, S. Sutherland & S. Troubetzkoy, Further travels with my ant, Math. Intelligencer, Vol. 17, pp. 48-56. 1995.

[6] A. Moreira, A. Gajardo & E. Goles, Dynamical behaviour and complexity of Langton’s ant, Complexity, Vol. 6, pp. 46-51. 2001.

[7] J.P. Boon, How fast does Langton’s ant move?, J. stat. Phys., Vol. 102, pp. 355-360. 2001.

[8] J. Gunn & M. Ortuno, Percolation and motion in a single random environment, J. Phys. A, Vol. 18, pp. L1095-L1099. 1985.

[9] Th. W. Ruijgrok & E.G.P. Cohen, Deterministic lattice gas models, Phys. Lett. A, Vol. 133, pp. 415-418. 1988.

[10] X.P. Kong & E.G.P. Cohen, Anomalous diffusion in a lattice gas wind-tree model, Phys. Rev. B, Vol. 40, pp. 4838-4853. 1989.

[11] J.C. Sommerer & E. Ott, A physical system with qualitative uncertain dynamics, Nature, Vol. 365, pp. 138-140. 1993.

[12] M. Woltering & M. Markus, Riddled basins of coupled elastic arches, Phys. Lett. A, Vol. 260, pp. 453-461. 1999.

[13] B.A. Toole, Ada, the enchantress of numbers, Strawberry Press, Mill Valley, CA. 1992.

[14] E. Goles & S. Martínez (eds.), Cellular automata and complex systems, Kluwer, Dordrecht. 1999.

[15] J.D. Murray, Mathematical Biology, Springer-Verlag, Berlin. 1989.

[16] M. Markus, Chaos in maps with continuous and discontinuous maxima, Computers in Physics, Vol. Sept/Oct, pp. 481-493. 1988.

[17] M. Markus & B. Hess, Lyapunov exponents of the logistic map with periodic forcing, Comput. & Graphics, Vol. 13, pp. 553-558. 1989

[18] M. Markus, A scientist’s adventures in postmodernism, Leonardo, Vol. 33, pp. 179-186. 2000.

a)

c)

d)

e)

f)

g)

i) Figure 2: Frieze-like patterns generated from Langton’s ant, after it was modified to respond to a periodically changing parameter.

j)

k)

l)

m)

n)

o) Figure 2 (continued)

p) r)

q)

s)

t)

Figure 2 (continued)

u) w)

v)

Figure 2 (continued)

Figure 3: Ant moving from a white to a black grid.

a)

b)

c) Figure 4: Ant tracks resulting from small perturbations of the forcing parameter $p$ .