 |
| John Horton Conway |
Contrary
to what is done with most scientific discoveries, Conway did not publish his
invention of the Game of Life in a typical scientific journal. It was first
published in the Mathematical Games section of
the Scientific American magazine, written by Martin Gardner. The article,
titled The
Fantastic Combinations of John Conway's New Solitaire Game 'Life', appeared
in the October 1970 issue.
 |
| John von Neumann |
Cellular
automata had been invented in 1948-49 by the mathematician John von Neumann,
famous for his numerous activities in the fields of computers (he designed the computer
architecture we still use, von Neumann machines, which separate
executable instructions from data); economics (he was one of the founders of
modern game theory); or the axiomatization of quantum mechanics
(although Dirac's version was finally adopted). A hypothetical capsule that
could help spread the human species across the galaxy is called a von
Neumann probe.
A cellular automaton is a discrete space
(usually two-dimensional, but it can have any number of dimensions) divided
into cells that form a potentially infinite grid. In each cell there is a
deterministic finite automaton that may be in a certain state, selected from
among several possible ones. Like space, time in the cellular automaton is also
discrete (i.e. it’s not continuous) and moves in steps of equal length. At each
step (or instant, or generation), the automaton of each cell receives information
about the states of the neighboring cells and changes its state according to that
information. All the automatons in the cells change state according to the same
rules.
 |
| The Game of Life |
In
Conway’s cellular automaton (the Game of Life)
each automaton can take only two states, which are called respectively alive
and dead.
The neighbors of each automaton, which send information about their state, are
eight: those located at a distance of one cell in any direction, horizontal,
vertical or diagonal. The rules to change the state are very simple: if the
automaton of a cell is alive, in the next instant it will
remain alive if it has two or three neighbors alive; otherwise, it will
go into the dead state; and if an automaton is in the dead state, it will go
into the alive state if it has exactly three neighbors alive.
It
is curious that a device as simple as the Game of Life
is capable of showing amazingly complex behaviors. By properly combining the
initial states of the automata, it has been shown that it is possible (though
not feasible) to build a computer that functions exactly like electronic computers
(albeit much more slowly). This cellular automaton can be divided into regions
that act as the logical gates with which the electronic circuits of a
microprocessor are built, so that, in principle, by combining a sufficient
number of these gates, a full computer could be assembled. This is why it is
said that the cellular automata of the Game of Life type are computationally complete, which means that, in
principle, any problem that can be solved with a computer, can be solved with
them.
Cellular automata and the game of life have many
applications in many fields. In a
previous article I mentioned that Francisco José Soler Gil and I used the
Game of Life and other similar cellular automata to prove that Tegmark's multiverse does not solve the problem of fine tuning.
- Equivalence
between cellular automata and Lindenmayer languages.
- Image
and sound processing by means of cellular automata.
- Evolving
cellular automata.
- Quantum
cellular automata for the simulation of neural microtubules.
Manuel Alfonseca
No comments:
Post a Comment