| Introduction to SCARLET |
"A cellular automata machine is sitting on our desk,
waiting for us to give a rule -
the law that will govern a world."
(T. Toffoli, N. Margolus)
When A. Turing in 1937 published his mathematical model of a computation
universal machine, he gave birth to a rapidly growing theory:
Other calculs as powerful as the so-called Turing machine were developed
soon.
About ten years later J. v. Neumann inspired by S. Ulam presented the
world his theory about ''selfreproducting automata''. It was his aim to show
a more practical way of constructing such computation universal machines.
Because of this suggestion he became the official inventer of
cellular automata (CA).
Roughly speaking he started out from a finite system which is discrete in time
and space and represented by finite state variables, called cells.
The cells are located in a finite and connected subset of a suitable
Euclidean space, for instance
.
Then the (global) evolution of the system is determined by the (local)
behaviour of its cells.
Furthermore he assumed the system to be homogeneous in space, that means
that every two cells behave the same way under the same conditions, which
are given by the states of certain cells in the
neighbourhood. The structure of the neighbourhood is supposed to be
identical for
all cells as well. Like that, the whole system can be described by a local
transition function, which is the same for all cells.
In spite of this promising idea, there was paid little attention to CA
for quite a long time.
Because of a lack of communication they were invented several times under
different names, and attempts to learn more about their properties went
unnoticed to other researchers, who sometimes did the same work again.
The situation changed only in 1970 by coincidence, when J. Conway attracted
the interest of many nonscientists, too, in a very special CA: the
Game of Life. At the same time, he focused once more on an
important application of CA: the simulation; a trend, which was also
supported by the developement of more powerful computer systems.
From then on up to now, some old as well as important theoretical questions
on CA could finally be answered, for instance, concerning their inversibility,
or their properties on language recognition, and so on.
But there were progresses made concerning simulation, too.
While it had been the main issue to investigate the global behaviour of CA in
order to classify them in the beginning, the inverse problem became more
and more of interest, especially for the natural sciences. They tried to
find out which of those CA models could be used to describe a piece of
reality, for example a physical system,
which is controled by certain laws of nature, which can usually be
described by partial differential equations.
Here the developement of models for particle movements in gases (lattice
gases) could be mentioned.
Inspite of these and other successes, a lot of important connections between
CA and their continuous counterparts are still lying in the dark.
Throughout the years, several modifications and generalizations of v.
Neumann's standard CA model were created to serve special needs:
the modeling of fluids or gases even lead to the construction of
probabilistic CA, which can exhibit distinct behaviours with certain
probabilities. Moreover we can find CA that are not simultaneously updated
(asynchronous CA), or that are
inhomogeneous concerning different aspects.
Analoguous to other concepts of computational theory nondeterministic CA
were investigated,
even hierarchical CA are used, just to name some types.
Although the abstract model on which CA are based is very simple, the
behaviour
they are capable to show can be so complex that it became almost enevitable
to employ simulation systems to deal with both theoretical and practical
issues.
Except for the cellular automata machines (CAM) developed by T. Toffoli
and N. Margolus to increase efficiency, most of those commercial or
noncommercial systems are just supported by software and designed for
different kinds of computers and operating systems. At the same time their
intentions vary: Some of them are restricted to special forms of the
standard CA (e.g., by just allowing certain neighbourhoods or space dimensions).
Others are mainly meant to model generalizations; there can be found a whole
lot of software packages that support probabilistic rules or spatial
inhomogeneity; and there exist even more creative concepts, but especially
those are often not intended for higher space dimensions, though.
SCARLET
at its present version 0.85 allows the simulation of
standard CA with almost no restriction at all.
Besides it permits the modeling of generalizations in a "natural manner"
(using additional states and the built-in
random function).
This manual is intended to be a guide for everybody who has somehow heard
about SCARLET and who would like to learn how to use it in order to solve
serious scientific problems or simply because of a personal interest in
CA.
So, we hope you enjoy SCARLET and wish you a lot of success!
| <webmaster@www.informatik.uni-giessen.de> | Mon Oct 26 11:50 MET 1998 |