Simulations can used to model occurrences such as regional growth, urban sprawl, population dynamics, economic activity and employment levels.
2)
Wolfram developed von Neumann’s one dimensional cellular automata. It was a horizontal line and each cell was adjacent to only two other cells, the immediate neighbours on either side. Each generation was represented by the line underneath the one it preceded. So if a cell was a part of the second generation the state it has would be determined by the corresponding cell in the first generation and the two neighbours it has. This would give eight possible states of those three cells:
000
001
010
011
100
101
110
111
When 0 means it is off and 1 means it is on. [5] This means that are 256 possible rules for the outcome of this cellular automata as mentioned in part one, some being as simple as all the cells are dead or they are all alive as Wolfram discovered when he studied the 256 possibilities.
Wolfram determined the behaviour of the thirty two legal rules in two ways; the impact on a cellular automaton which has an initial state of a single one cell and the impact with an initial state which is random. [8]
So [8] uses rule eighteen as an example; 0 1 0 0 1 0 0 0 as rows three and seven are identical making it a legal rule.
Restrictions do arise though. If the cellular automaton is infinite it has ‘ends’ which therefore mean the cells at the edge do not have the same neighbourhood as the cells in the middle. These can be treated differently or be thought of a close ‘ring’ to give uniformity of the neighbourhoods. The best method is to consider work with symmetric neighbourhoods that focus on each cell.
Cellular automata are however often a lot simple in the behavioural patterns than the real life situation they are mimicking.
This is where Wolfram’s notation (k,r) arises in linear cellular automaton where k represents the states within the cells and r is the cells on either side i.e. the neighbourhood. [6]
Wolfram derived four classifications which were types of behaviour that were relevant to dynamic systems of cellular automata. [7] Research has shown that all one dimensional cellular automata fall in to one of these four categories.
Class 1: Systems will generate uniform behaviour like convergence
Class 2: Systems exhibit repetitive behaviour
Class 3: Systems that exhibit random or chaotic behaviour
Class 4: Are the systems which fall in between in classes 2 and 3.
A one dimensional state, image taken from Cellular automata and geosimulation Url:
In class one the solutions to differential equations can be obtained with any initial conditions which approach a fixed point. The initial states give a unique homogenous state and all initial states yield the same final state. In this case a species usually becomes extinct.
In class two for second class of differential equations the limiting solution is a cycle in which the parameters vary with time. It also gives separate structures but the final state only depends on a finite region of the initial state. This is population growth usually in a predator prey situation.
In class three with the initial conditions being specified by decimals and solutions depend on the higher order of digits in the initial conditions. The solutions in this class are often chaotic attractors. The effects of the changes occur forever at a finite speed.
The fourth class exhibits the most complicated behaviour and are conjectured to be capable of universal computation. Regions of the final state depend on large regions of the initial state.
The behaviour of these classes found in cellular automata and those found in continuous dynamical systems support the generality of these classes.
The simplest one dimensional cellular automata is binary and derived by the nearest neighbour idea. Such automata was named by Wolfram "elementary cellular automata"
Image from www. Cellular Automata\Cellular Automaton -- from MathWorld.htm
3)
Game of Life was invented by John Conway who was a mathematician based at Cambridge University. It is played on a board of tessellated squares and each square is a cell. These cells are either alive or dead. Their neighbourhood is the surrounding cells and they determine the state of the next generation of cells.
So the next generation would look this due to loneliness since each cell only has one neighbour.
It is important that deaths and births occur simultaneously as accumulatively they form the generation.
The best way to play the game is with two sets of counters that differ in colour.
- Decide which counters represent the dead cells and locate these in to the chosen squares.
- Then work out which cells are born.
- Double check to see if any mistakes have been made. This is the first generation.
These steps are repeated for each generation. The Game of Life is a simple demonstration of cells obeying the set rules. This gives us the simulation of real life.
From the changing population various patterns will occur. In very few cases the population dies out all together although this does not happen until many steps (generations) have been completed. Some patterns become still and do not move others simply oscillate.
One of the most common patterns to form is called the R-pentomino which is also known as a glider. It originally begins with just 5 cells hence the name but gets complicated very quickly.
It is important that deaths and births occur simultaneously as accumulatively they form the generation.
There are several different shapes which occur in Cellular Automata, these form different systems.
There are many applets on the internet which show how this develops over generations to become much more complicated. They also show how the name glider comes about as they glide along the cells until they disappear “off the edge”. This shape was the first to be defined by Conway and can be predicted but not until 1103 steps have taken place.
Gliders were first found by Conway in 1970
Glider guns are states that do not die out nor do they stay still. These can be seen below ‘gliding’ across the screen as the name suggests.
Many starting points in the Game of Life will eventually give out gliders.
A gun is a pattern that grows forever by emitting spaceships (the gliders) which is any pattern that moves without leaving a trail.
Both the above images taken from .
It is possible for gliders to interact with other objects for example if two gliders hit one another at the right angle they will move closer to their source.
Guns and spaceships are created by replicators which can be defined by shapes which are able to make copies of itself. Replicators can also build other patterns such as period oscillators, puffers (a variation of spaceships) and pseudo random, number generators.
Many of these replicators work according to an parity rule which is a grid, usually in one dimension of possible replicators positions. They are placed in places so that they produce new replicators at the positions with an odd number of replicators in neighbouring cells. [16]
4) I have designed my own forest model by setting up a 3*3 matrix. The values in this matrix had to add up one so I used Excel’s ability to be able to add numerical values to check this for each column.
Using “if” statements I was able to set up three separate grids, with 0s and 1s, 0s and 2s and finally 0s and 3s.
The bottom grid at the left hand side contains random numbers to allow a random state in the automaton.
The 3 grids which have no colour coding on the right hand side are used to calculate the values in the coloured grid at the right hand side.
At present looking at My_Foreset.xls sheet named Forest2 there is a group of “2s” in the top right hand corner. This could be a boulder, hill, lake or another static form in a forest. When the macro is run this state remains the same in the coloured grid on the left hand side.
5)
There are three main ways in which cellular automata models can be extended. The first is introducing migration. In the forest model the values are fixed to a particular location and there is one value (item) per cell. By introducing migration we allow the items to move across the cell. We would also need to decide if there is going to be one item in a cell or allow two or more to share a cell. [17]
Another extension could be to allow items to be affected by more than their immediate neighbours and to be influenced by any actions which affect the whole grid or the other items in the grid. [17]
Thirdly the items that have been looked at so far have no memory. Models can be built in which information preserved and used to calculate the next state on the basis of their neighbours. [17]
6)
7) Group work with Claire Lovell and Laura Walters
References
[1] Cellular Automata URL: Last accessed 27/01/2004
[2] Rucker, Rudy and Walker, John, Cellular Automata Library, Url: Last accessed 27/01/2004
[3]
[4]Hogeweg, P,
[5] Wolfram and 1-Dimensional Cellular Automata URL: Last accessed: 07/02/04
[6] One Dimensional Automata, URL:
[7] URL:
[8] Cellular Automata, Spillman, Richard URL:
[9] Wonders of Math - The Game of Life, Callahan, Paul, URL: Last accessed: 13/02/04
[10] Mathematical Games - The fantastic combinations of John Conway's new solitaire game URL:
[11] Conway's Game of Life URL:
[12]
[13] Artifical Life – Cellular Automata URL:
[14] Conway's Game of Life – Wikipedia .
[15] A Cellular Automata Prgoramming Environment for Computational Steering
[16] Cellular Automata: Replicators
[17] Extensions to the basic model
http://www.uni-koblenz.de/~kgt/learn/textbook/node77.html
.
.
advantages and disadvantages of the cellular automata approach to modelling
cellular automata, strange attractors, chaotic attractors
cellular automata as a paradigm to dynamical systems
examples of Wolfram's classification
Loktra Voltera predator prey models
