Domain of cellular automata: definition, history, relation to AI
Definition
Cellular automata consist of cells, connected to each other in a grid.
Such a grid can have any dimensions and sizes. To start easy, we consider
for now finita cellular automata in two dimensions. Such an automaton has
a structure like a chess-board
.
The fields in the chess-board can be of different colors or states. A cellular automaton
goes through iterations:
On discrete moments each field from the grid is re-colored, based on the colors
of its immediate neighbours. Those immediate neighbours are the fields above, under
to the left and to the right of the considered field.
How are those re-colorings settled? To accomplish that, a cellular automaton uses a transition-function.
It is a function that takes the old states of the neighbours as input and returns the new state as output.
In our case of four immediate neighbours and color-states we are speaking of a projection from four
colors to one color. The transition-function of a cellular automaton is the same for each cell.
As a clarification, here is
a first example
with the simple rule that a field becomes red (in a new iteration) if one of its immediate neighbours
is red (in the current iteration). Fields with only white neighbours become white.
We start with one red field in the middle. For easy orientation, it is marked. Each new grid represents
the state of the cellular automaton on a next discrete moment in time.
Mind the 'flipping' state of the marked field.
Parameters
With the previous example we took a lot of things for granted. However, many variations are possible.
The following concepts are potential parameters for an actual cellular automaton:
Dimensions
How much dimensions must the grid have? In stead of two dimensions (a chess board), we can consider
any amount of dimensions. If the cellular automaton exists in only one dimension, all cells
are in one row. In case of three dimensions, the cells are not just part of one field, but
in different fields above and under each other.
Sizes
How large is the grid in each of its dimensions? If the amount of dimensions is chosen,
we still do not know how large the cellular automaton is. The cellular automaton can be of infinite length
or finite length in each of its dimensions. A potential relevant choice in case of two dimensions
is letting each dimension have the same finite length, so: a chessboard. The same choice in each
dimension n has the result of a n-dimensional (hyper)cube. In the trivial case of one dimension
it is a finite line.
Neighbourhood
How should we realise the notion of neighbourhood? That notion specifies for each cell which
cells are its neighbours.
To do so, the relative positions of neighbours are considered from the perspective
of a certain cell.
Since we consider relative positions, the notion of neighbourhood has the same realisation for each cell
of the automaton. That is right, since the transition-function based on the notion of neighbourhood,
has to be the same for each cell by definition.
Typicaly the neighbours are just those cells euclidically closest to the considered cell.
In one dimension this means the cell immediately left and immediately right. In two dimensions
the cells above and under are added. In three dimensions the cells in front and at the back
are also added. So, in n dimensions, within an n-dimensional hypercube, typically 2^n (immediate)
neighbours are added.
The previously described neighbourhood is called a Von Neumann-neigbourhood. In certain situations
it can also be useful to consider more or less neighbours (although seldomly less).
For instance, if we also consider the diagonally closest neighbours, we speak of Moore-neighbourhood.
States
The number of potential states is also a possibility for variation in the definition of a cellular automaton.
This number is at least two, since otherwise we cannot even speak of an automaton
- there is no possibility to change the global state.
Wrap around
What should we do with the cells at the edge of the board? They don't have as many neighbours as the rest.
We can simply restrict the working of our cellular automaton at the edges:
rules working on non-existing cells (EG richt-neighbour of mostright cell),
will not be applied.
However, there is another possibility: we can connect the edges. In one dimension this means that
the mostleft and the mostright cells have each other as neighbour. In two dimensions the
right neighbour of the mostright cell is the mostleft cell at the same heigth. In the common case
the heighest coördinate, which is normally increased by 1 to determine a neighbour, is reduced to
zero, since there exists no heigher coördinate
The resulting structure in one dimension is a circle. In two dimensions the result is a torus.
Imagine that the board is flexible and that we fold it until the upper and bottom edges touch each other.
The result is a cilinder. If we want to connect the other edges as well, we have to fold the cilinder
until the edges touch again. The structure that arises then is called a torus.
We can still represent the cellular structure two-dimensional with some imagination.
A central cell has neighbours which are also visual-intuitive its neighbours on the grid.
A cell at the edge has neighbours at each side of the grid. All of this becomes clear in the following
illustration
, in which a colored circle is a considered cell and a cross in the same color one of its neighbours.
A cellular automaton, seen as a torus and with three states for each cell, is presented here in
a second example
. In this example each cell has eight neighbours (Moore-neighbourhood). Besides the four 'straight' neighbours,
we also consider the four diagonal neighbours. Each cell has three potential states or colors: white, blue or red.
To determine the new color of the cell we count how many (Moore) neighbours have the color blue and how many
have the color red. If more neighbours have the color blue, the cell becomes blue in the next iteration.
If there are more red neighbours, the cel becomes red. If the amount are equal, the cell becomes white.
History
John Von Neumann
John Von Neumann was born in 1903, in Budapest. Already as a seventeen-year old he became an active scientist,
which he remained until his early dead from cancer in 1957. John Von Neumann was a genius,
active on many fields, like quantum mechanics, nuclear research and the development of
the modern computer.
John Von Neumann was a co-worker at the american Los Alamos-project in 1943, for the development
of the nuclear bomb. His contribution consisted mainly of the mathematical modelling of nuclear processes.
The experience he acquired during the Los Alamos-project helped him to push the development
of the modern computer.
Back then, computers were almost completely seen as huge calculators, with no other potential applications
besides simple computation. Von Neumann however, saw much more possible applications.
It was his idea to place data and code at the same level. Until then, data of a program
had always been strictly seperated from the instructions of the program. Von Neumann was the first
to understand fully that, through appropriate encoding, data and instructions could be placed
in the same physical memory.
Von Neumann wanted to introduce computers in all fields of science, to bring in more logics
and exactness into science. It is partly due to his many contributions to the architectural
development of the computer that today many of his dreams have become reality.
However, Von Neumann dreamt also of applications for the computer that are out of reach, even today.
The idea that from the very simple logical rules of the computer yet very complex behaviour
can arise, Von Neumann found very intriguing. It even led him to believe that all live was
based on simple logical principles. He tried to show that the life like it exists around us,
and like we are ourselves, can be modelled with automata.
For his studies about the potential modelling of life Von Neumann used cellular automata.
Von Neumann saw the capability to self-reproduce and evolve as the most important characterisation
of life. The question whether self-reproduction by automata was possible, he solved
by his modelling of a self-reproducing cellular automaton. However, Von Neumann died at cancer
in 1957, without finishing his search to the potentiality of life in cellular automata.
Ulam
It is thanks to the help of the matematician Stanislaw Ulam (1909-1984) that John Von Neumann used
cellular automata for his self-reproducing automaton. To Von Neumann it was already certain before
his use of cellular automata that self-reproduction was possible for automata, by holding a 'blueprint'
in the automaton. The blueprint was to be kopied exactly and was needed for buildinginstructions
of the automaton. So: such a blueprint would have the same function as our DNA. By lack of a good
environment to develop such an automaton, Von Neumann could not make his idea credible to the public.
Ulam worked together with Von Neumann at the Los Alamos-project. That is why they were close enough
to support each other. Ulam came with the idea of an abstract space of cells with a finite number
of states. During iterations the cells had to influence each other locally and uniform
The genius Von Neumann quickly found a self-reproducing cellular automaton, thanks
to Ulams contributions.
Conway
In 1970 John Conway - mathematician at Cambridge - published his 'game of life'.
It is a two-dimensional cellular environment with two possible states for each cell in which
initial patterns seem to act 'alive'. Smal concentrations of black cells (state 1)
get spread. Concentrations that get to large, die(become white or go to state 0).
More about Conways Game of Life follows in the part
about simulation and artificial life with cellular automata.
Simulation and relation to AI
A crucial notion is emergence. It means: unexpected global complex behaviour by cummulation
of locally simple effects. An emergent phenomenon is for instance the forming of crystals.
Emergence occurs a lot in cellular automata. Conways 'Game of life' is a good illustration of it.
Very simple rules yet have a surprisingly complex behaviour as a consequence.
Certain emergent phenomena are already successfully simulated by cellular automata.
Cellular automata proved their simulation-value in numerous fields, like
ecology, biology, weatherforecasting...
Emergence is also a crucial part of AI, since intelligence is a typical emergent phenomenon.
It seems for instance that we understand the working of one neuron, but we don't seem to grasp
the global working of our brains. Also evolution an other 'learning' processes have
with cellular automata in common that the basic rule are simple, but
the global result is hard to grasp.
Cellular automata seem very useful to AI. What seems typical for (artificial)
intelligent mechanisms, namely simple commands with an amazing impact
- so: emergence, is certainly an aspect of cellular automata.