Simulated Life and Mathematical Abstraction: Emergent Behaviour, Emerging Concepts
‘Consider an infinite two-dimensional square grid.’ It does not have the same impact as the old physics joke of ‘assuming a spherical cow in a vacuum’ (1) in terms of humour (or at least, science humour), but the statement may well seem equally absurd. For a start the mind cannot truly visualise anything infinite; we only ever perceive and process a finite part of the universe at any given time. We may have a vague sense of the vastness which exists beyond our perception, whether finite or infinite, but we cannot see it.
In trying to understand the original statement, it is therefore most productive to separate the concept of ‘infinite’ for now and think instead of ‘two-dimensional’ and ‘square grid’. These concepts are much easier to visualise: our minds are likely to convert ‘two-dimensional’ to flat, and a ‘square grid’ to a grid made up of squares, rather like an uncoloured chessboard but with an unspecified number of squares. We can aid our understanding of the statement by exchanging an ‘infinite two-dimensional square grid’ for an ‘extremely vast chessboard’.
It would not be generalising too much to say that breaking down the individual mathematical terms and thinking about them separately can improve the understanding of the concept by a wider audience. It is also helpful to consider the terminology in layman’s terms. However, mathematicians have felt the need to formulate their own language for their discussion of the concept and, in this example, we see that the mathematical language implies an object more general in nature than the simplified ‘vast chessboard’; information would be lost if we were to discuss only in terms of chessboards. Frequently, mathematicians create abstractions of other concepts in similar fashion, developing a new idea or principle that can be manipulated mathematically. Any results arising from analysis of the idea can then be applied to several scenarios, including those from which the concept originally emerged.
However, my reasons for introducing this ‘infinite two-dimensional square grid’ were only partly to discuss the general emergence of mathematical concepts. This grid also serves to introduce one of the classic examples of a system exhibiting ‘emergent behaviour’: John Conway’s Game of Life (hereafter ‘Life’). Emergent behaviour can be thought of as a generalisation of emergence as the abstraction and combination of ideas (as we have combined the individual concepts of ‘infinity’, ‘dimensions’ and ‘square grid’ to form an object quite different as a whole from the parts used to define it above), rather than of emergence within any one stand-alone branch of ideas; it is defined as ‘patterns and properties [of a system] that just cannot be predicted from knowledge of their parts taken in isolation’ (2). That is to say, given knowledge of the rules that feed into and describe a system, emergent behaviours are those elements of the system which occur as a result of the interactions between the rules, rather than the individual rules themselves.
Life is ‘played’ on our ‘infinite two-dimensional square grid’ or ‘vast chessboard’, operating the following algorithm (3):
1. Each square on the grid is defined as a ‘cell’; each cell can be either ‘alive’ or ‘dead’.
2. The neighbours of each cell are defined as those cells directly adjacent vertically, horizontally, and diagonally.
3. Apply these rules to each cell simultaneously:
a. Any live cell with fewer than two live neighbours dies (underpopulation);
b. Any live cell with more than three live neighbours dies (overpopulation);
c. Any live cell with two or three live neighbours continues to live (survival);
d. Any dead cell with exactly three live neighbours becomes live (reproduction).
4. Repeat step 3. ad infinitum (each repeat is akin to one new population generation for the system).
It would be fair to say this is probably not what most people would consider a ‘game’; the only time a ‘player’ can interact with Life is by choosing the initial state of each cell as alive or dead, before steps three and four, which alter the states of the cells, come into effect.
The system was devised around 1970 by John Conway, a pure mathematician with an interest in recreational mathematics and puzzles (4). His original motivation was to condense the essential characteristics of how living organisms reproduce into a model easy to simulate computationally. Being a mathematician, Conway also desired unpredictability in the behaviour of the system, in that from a given configuration of alive and dead cells in the Life system, it should be difficult to predict future states of the system after many generations. This would include the characteristic that even simple patterns (of a few live cells across a small region in the system) should lead to non-simple future states.
As an example, consider the image below as part of a random initial setup of Life (5), where blue cells are alive and white are dead, with all cells not pictured (off the edge of the grid) dead – as they are all dead, they will stay dead and need not be considered:
If we now apply the algorithm, the next ‘generation’ looks like:
Although the live cells occupy the same general region of space, the distribution of the live and dead cells is significantly different; it would be extremely difficult to predict that this is the distribution which would arise from the initial setup, other than by applying the rules and seeing what happens. This unpredictability is typical of the many existing systems exhibiting emergent behaviour in fields as diverse as ant colonies (6) and stock market modelling (7), to name only two.
As we advance to future generations, the system begins to look less and less like the initial state; the image below snapshots this part of the system at generation 250.
It is not apparent by observation that these states are linked by evolving through several generations of Life, and rules 3a, b, c and d could not individually have informed us that generation one would evolve into generation 250, for example; it is the combination of these rules which induces the behaviour, and thus it can be described as emergent.
Interestingly, there are local distributions of live cells which change at each generation, but change back to their original configuration at a later generation: a periodic pattern. There are also groups of live cells which appear to move across the grid in an ordered manner such as the ‘glider’, an animation of which is at (8). One example of a periodic pattern is a horizontal line of three live cells which alternates between horizontal and vertical three-cell lines at each generation, some examples of which can be found in the image below. Such patterns exist as a result of the interaction between the multiple rules in effect, and are thus an emergent behaviour. This image is also the long-term pseudo-steady state of the system in that, aside from the alternating three-cell lines, the system will never change in the future no matter how many iterations of the algorithm are applied; the fact that such a state exists is another unpredictable, emergent behaviour of the system.
Whilst Conway’s Game of Life is a rather abstract concept, it is mathematically rich for a system described by so few rules, and is just one example of a system exhibiting emergent behaviour. Many other systems which can have a variety of real-world applications also show this complex behaviour. By its definition emergent behaviour is extremely difficult to predict; individual rules of a system may be well-understood, but the possibilities for interaction between several rules are vast. It is this intrinsic difficulty, together with the many physical scenarios in which emergent behaviour arises, which has caused emergent behaviour to intrigue many fine minds of the past and will ensure it continues to intrigue in future.
References:
(1) http://www.physics.csbsju.edu/stats/WAPP2_cow.html
(2) http://www.britannica.com/EBchecked/topic/130050/complexity/129407/Uncomputability#toc129410
(3) http://www.conwaylife.com/wiki/Conway%27s_Game_of_Life#Rules
(4) M Gardner, Mathematical games: The fantastic combinations of John Conway’s new solitaire game “life”, Scientific American 223.4 (1970): 120-123.
(5) Produced using http://pmav.eu/stuff/javascript-game-of-life-v3.1.1/
(6) GE Marsh, The Demystification of Emergent Behavior, arXiv:0907.1117
(7) S-H Chen and C-H Yeh, On the emergent properties of artificial stock markets: the efficient market hypothesis and the rational expectations hypothesis, Journal of Economic Behavior & Organization 49.2 (2002): 217-239.
(8) http://www.conwaylife.com/wiki/File:Glider.gif