Here is one physicist's view of the relevant definitions:
A cellular automaton is a discrete dynamical system. Space, time, and the
states of the system are discrete. Each point in a regular spatial lattice,
called a cell, can have any one of a finite number of states. The states of the
cells in the lattice are updated according to a local rule. That is, the state
of a cell at a given time depends only on its own state one time step
previously, and the states of its nearby neighbors at the previous time step.
All cells on the lattice are updated synchronously. Thus the state of the entire
lattice advances in discrete time steps.
Here is one mathematician's view of the relevant definitions:
Conventions d=dimension, k=states per site, r=radius (all explained below).
For simplicity, assume d=1 for the moment.
A d-dimensional cellular automaton takes as its underlying space the lattice
(Z=integers, infinite in both positive and negative directions)
where S is a finite set of k elements. The dynamics are determined by a global
function
whose dynamics are determined ``locally'' as defined below.
A ``local (or neighborhood) function'' f is defined on a finite region
The all-important property of cellular automata, is that this function is
determined by a finite lookup table. Both the domain and range of f are finite.
The global function F arises from f by defining:
A concrete example with k=2,r=1 would take a doubly infinite string of zeroes
and ones to a new string at which each site is replaced by the logical and of
its two neighbors (Wolfram's elementary rule 90).
Some relevant facts from a topological standpoint are:
The base space
is compact and the global function F is continuous.
To insert an editorial comment, this makes CA an ideal meeting point
between continuous dynamics and complexity theory, since they are discretely
defined but exhibit continuous dynamics.
The map F commutes with the shift operator which takes
to .
In fact cellular automata are characterized completely by properties 1) and
2) (Hedlund).
The transition to more dimensions is straightforward. The only difference is
that the global function F is defined over
(functions from a d-dimensional lattice to S) and the local function f is
determined by enumerating the image of all patches of size
.
For an introduction to CA, some of the more well-known references are:
This question sparked an interesting discussion on the CA list a while back.
Some, noting the difficult job market for scientists, and the ill-repute of CA
in some circles, replied, "Nothing, if you want to get a job." Some more upbeat
and constructive remarks follow.
Boghosian: Lest today's funding realities make us too somber and
cynical, I offer some words from George Bernard Shaw:
"The reasonable man adapts himself to the world; the unreasonable man
persists to adapt the world to himself. Therefore, all progress depends on the
unreasonable."
I certainly agree that grad students should be well informed about their
options if they elect to pursue a dissertation in a nontraditional field such as
cellular automata. I would, however, strongly disagree with the allegation that
nontraditional research tends to be of lower quality.
For every one "free thinker" that succeeds, there may be fifty that do not
and retreat to the mainstream, but there are many examples of key advances in
science that would simply never have happened if those fifty people had not been
willing to stick their necks out a bit and try something new.
Wolfram:
Here is a list of questions about cellular automata that I discussed in my
1984 paper: "Twenty Problems in the Theory of Cellular Automata", published in
the proceedings of the 59th Nobel Symposium, and reprinted in my book: "Cellular
Automata and Complexity: Collected Papers" (Addison-Wesley, 1994):
1. What overall classification of cellular automata can be given?
2. What are the exact relations between entropies and Lyapunov exponents for
cellular automata?
3. What is the analog of geometry for the configuration space of a cellular
automaton?
4. What statistical quantities characterize cellular automaton behavior?
5. What invariants are there in cellular automaton evolution?
6. How does thermodynamics apply to cellular automata?
7. How is different behavior distributed in the space of cellular automaton
rules?
8. What are the scaling properties of cellular automata?
9. What is the correspondence between cellular automata and continuous
systems?
10. What is the correspondence between cellular automata and stochastic
systems?
11. How are cellular automata affected by noise and other imperfections?
12. Is regular language complexity generically non-decreasing with time in
one-dimensional cellular automata?
13. What limit sets can cellular automata produce?
14. What are the connections between the computational and statistical
characteristics of cellular automata?
15. How random are the sequences generated by cellular automata?
16. How common are computational universality and undecidability in cellular
automata?
17. What is the nature of the infinite size limit for cellular automata?
18. How common is computational irreducibility in cellular automata?
19. How common are computationally intractable problems about cellular
automata?
20. What higher-level descriptions of information processing in cellular
automata can be given?
Most of these questions have now received at least some attention, but still
none can really be considered solved. My own research over the past several
years would lead to me to formulate slightly different questions, but I think
the ones above are nevertheless a useful starting point.
And if anyone manages to come up with a definitive solution to any of these
questions, I can say that I at least will be very interested in hiring them!
- Stephen Wolfram
McIntosh: Possibly the field is less active than it used to be,
something which can be judged by the volume of CA-Mail in comparison with past
years. For one thing, lattice gasses have split off from cellular automata, and
then the support for the kind of hydrodynamics which requires lattice gasses may
have diminished. For another, the a-life group was created, carrying with it an
activity which was related to cellular automata, although not strictly a part of
it. And then there are neural networks, Petri nets, Lindenmayer systems, and so
on. So there is much to choose from, in areas generally related to automata.
The topics which Howard Gutowitz covered in his own thesis have still not
been exhausted; there was another similar thesis (published as Wilbur, Lippman,
Sharma, "on the prediction of local patterns in cellular automata" in the same
time frame of ten years ago), but things seem to have been left where they were
back then.
To a certain extent, everyone managed to show that a sophisticated treatment
was considerably harder (or at least computationally more involved) than the
naive treatment. Gutowitz, Victor, and Knight also ventured to two dimensions,
again finding that the problems there were harder, especially in dealing with
Kolmogoroff's requirements for subdividing probabilities.
Now that time has elapsed, understanding has grown, machines are faster, and
programs are better, there could be an opportunity to return to the topic -
which consisted in getting good probability measures to describe automata and
their evolution. How good? Studies on binary automata exist; would anything
(like better statistics) be gained by working with more states? Is the Wolfram
classification scheme adequate for these automata? Can we make do with mean
field theory, especially by recognizing its limitations (avoid totalistic
rules)?
And speaking of the avoidance of totalistic rules, is there a reason why
someone should not concentrate on totalistic rules and try to derive their
special characteristics? For starters, sums might be thought to obey a Gaussian
distribution, but empirical evidence suggests a more nearly uniform
distribution.
The (not now so recent) work of Chaté and Manneville opens up a whole new
world of automata, both experimentally and theoretically. Phenomonologically
they have something like semiconductors, wherein a small amount of impurities
can substantially modify the overall evolution of an automaton. Someone who
wanted a nice project could try to find out more about the kinds of automata
exhibiting the effect, practical ways to manage the impurities, and above all
try to find an adequate theory to describe them and predict their behavior.
The problem is that classical iteration theory just doesn't apply to this
class of automata, but yet there is regularity to be seen at work. One loses the
theorems about conservation of fixed points and counterimages of critical
points, but surely there is something which could take their place for composite
rather than iterated functions?
Even for classical automata like Life, there are practical and philosophical
problems which could be approached by having available an adequate theory of
composite functions. Questions of long term evolution - not hundreds or
millions, but zillions, of generations - need an adequate theory of limits
before speculations can be tested and made reliable. Will a Universal Life
computer EVER evolve spontaneously, under any reasonable (or unreasonable)
conditions?
This is probably way beyond the range of a Ph.D. thesis.
Even if the thesis project were not to explore new theories or new aspects of
old theories, there is certainly a use for programs which will calculate answers
to all the questions which can be asked about automata. This might result in a
project more worthy of Computer Science than Mathematics. Of course it is true
that several programs already exist; nevertheless computer technology keeps
advancing, bringing with it the possibility of having better programs, or even
just programs with better interactive potential. Or more widely available for
different platforms (to use a buzz word).
Visual display keeps getting better and better, so effective presentation of
three dimensional automata is more feasible than it used to be. Not only might
this aid the seardh for three-dimensional Life, it is also the proper domain of
the Chaté-Manneville automata. Not to mention carrying Belusov- Zhabotinsky
reactions into three dimensions. Again this may be more of an engineering or
computational thesis than one in physics or mathematics; well, the request was
for topics, without specifying with which faculty or school.
A person seeking a thesis topic might do well to see what topics have proven
successful in recent years, either to use them as a model or even to decide on
what to avoid. Two more which come to mind were written by Lyman Hurd and Jarkko
Kari, respectively. The former was concerned with the limit sets which could
arise under long time evolution, mostly of one dimensional automata, and so
related to the limiting evolution problem already mentioned.
The latter made a highly regarded analysis of decidability problems in two
dimensions (and, by inference, beyond). This may or may not have exhausted the
topic, but one thinks not.
Maybe some final words on the politics of thesis choice are in order.
Obviously it would be prudent to take into account the interests of the faculty
members of the Department in which one intends to write the thesis. A
sympathetic advisor is evidently a considerable asset. On the other hand, it is
one's own life and education which is at stake, not the professor's. There will
be far fewer opportunities to study something in which one is particularly
interested outside of the university environment than within it. Therefore the
selection of a thesis topic ought to reflect one's own interests; it is alright
to ask around for ideas or suggestions, but in the end it is the person who
writes the thesis who is going to have to make the decisions as to what it will
contain, what its orientation is to be and so on.
As far as the choice of a thesis topic affecting job opportunities, there is
no doubt that there is going to be some correlation. Still, there is always the
question of why one is studying in the first place? Is it to learn something
about the world, or is it to get some preliminary job training? How many people
have the opportunity (or the desire) to follow up their thesis work in later
life?
Somehow, a thesis is supposed to culminate a program of graduate studies by
demonstrating that its author has dominated several skills, such as making a
sensible choice of level and theme, the ability to make a survey of the
literature, the ability to write a scientific document with a certain minimum of
literary merit, and, of course, to make an original contribution to the body of
scientific knowledge.
A sensible employer will judge the degree to which these criteria have been
met; offering employment in kind will probably seem less important than trying
to judge whether the prospective employee is alert, intelligent, versatile, ...
. If the original goal was to prepare for technical employment, there should be
no conflict. Having grown fond of the thesis topic and wanting to specialize
immediately in following it up, the recent graduate is likely going to have to
be more aggressive and persistent. Does this come as a surprise?
A journal devoted to the rapid publication of research on the science,
mathematics, and engineering of systems with simple components but complex
overall behavior.
Editor: Stephen Wolfram, Wolfram Research, Inc., and University of Illinois
What is the AMS classification for CA?
Contributions by: Mike Hurley mgh3@po.cwru.edu
68Q80 is Computer Science / Theory of computing / Tessellation automata,
iterative arrays, cellular structures
58F 08 is Global analysis, analysis on manifolds / dynamical systems / point
mapping properties; ...; dynamics of cellular automata.
J. D. Farmer, T. Toffoli, and S. Wolfram, editors. Cellular Automata:
Proceedings of an Interdisciplinary Workshop at Los Alamos, New Mexico, March
7-11, 1983, Amsterdam, 1984. North-Holland. A collection of papers
on the theory and applications of cellular automata.
Andrew Wuensche and Mike Lesser. The Global Dynamics of Cellular
Automata, volume Reference Vol 1 of Santa Fe Institute Studies in the
Sciences of Complexity. Addison-Wesley, 1992. IBSN 0-201-55740-1.
S. Wolfram, editor. Theory and Applications of Cellular Automata.
World Scientific, Singapore, 1986. Collection of papers on CA's.
Contains an extensive bibliography.
Stephan Wolfram. Cellular Automata and Complexity: Collected
Papers. Addison-Wesley, 1994. revision of [Wol86]
Paperback: ISBN 0-201-62664-0, Hardcover: ISBN 0-201-62716-7.
(Z=integers, infinite in both positive and negative directions)
where S is a finite set of k elements. The dynamics are determined by a global
function
is compact and the global function F is continuous.
to 
.
(functions from a d-dimensional lattice to S) and the local function f is
determined by enumerating the image of all patches of size
.