Cellular Automata¹

Introduction

As soon as Galileo began to apply mathematics to the study of the world, complications arose. Actually, the complications had always been there - but now scientists and mathematicians came face to face with them. The way that scientists and mathematicians deal with nature's complications is generally simple - they ignore them. Right away, scientists realized that the systems that they study need to be simple systems, because often very complicated and sophisticated mathematics is needed to model even a very simple system. To accurately model a car accelerating away from a stop light, the motion of a pendulum, or the fall of a raindrop, for instance, involves calculus and differential equations - at least. Scientists need to reduce a situation to points, straight lines and smooth curves in order to bring the power of mathematics to bear on it - the problem being that nature prefers blobs to points, and random-looking zigzags to straight lines and smooth curves. Simple mathematics will only deal with the most trivial of problems - therefore, it must take enormously powerful and abstract mathematics, far beyond our current human capabilities, to deal with the complexity of nature.

To look at this from another direction, computer programmers know that it can take a fairly-sophisticated computer program (the set of rules that tell the computer what to do) to get a computer to do even very simple tasks. If you want the computer to do something complicated, it will, of course, require an enormous and intricately-detailed program. The assumption is that very simple programs can only do extremely simple tasks.

Here are some questions that these pages will try to address:

• How complicated does a model (system, or set of rules/instructions) have to be before it can generate complicated behavior?
• Can very simple systems with very simple rules do very complicated things?
• Can very simple programs do very complicated things?
• The number is simply the ratio of the circumference of a circle to its diameter: . Yet, is a very complicated number - in the couple of billion digits of that have been calculated, no meaningful patterns have ever been found. Why? How can such a simple definition produce such a complicated result?
• Looking at things from another direction, how complex does a system need to be to take random, chaotic inputs and produce organized, regular outputs - to produce order from chaos, in other words?

The branch of mathematics that deals with the behavior of simple finite systems is "automata theory". An automaton (aw-TOM-u-tahn - the singular of "automata") is a system that "does its thing" automatically, based on a few, simple rules. An everyday example of an automaton is a computer. You probably think of a computer as a very complicated device (and it is!), but deep in the "heart" of its CPU the computer has a very small set of simple instructions (usually no more than a couple of dozen) that it follows. The computer can follow these instructions very rapidly, however, and in so doing perform very complex actions.

The study of automata has produced insights into very diverse fields - mathematics, physics, biology, economics, and computer science, to name a few. It has also contributed to the study of the theory of computation, operation of neural networks, study of traffic flow, interaction of individuals (human and animal) in groups, turbulence, fluid flow, cryptography, distributed computing, and even the nature of life itself. In this short unit, we will study elementary cellular automata in one and two dimensions and see what we can learn about these simple, yet fascinating systems.

A Little History

John von Neumann (source: Wikipedia

You may never have heard of the mathematician John von Neumann, but you should have. von Neumann was the person responsible for the architecture of the modern computer (CPU, memory, I/O) in addition to many other contributions to mathematics. In the 1940's, von Neumann was working on the problem, "How can you design a robot that can, completely on its own, manufacture replicas of itself?" As he got deeper and deeper into the problem, he found it more and more intractable. His friend and colleague, Stanislaw Ulam, was working on a mathematical model for the growth of crystals and was using a rectangular grid to model the process. Ulam suggested that working with such a grid might help von Neumann work out the theoretical difficulties of his"self-replication" problem. In this way, a new branch of mathematics was born - the study of cellular automata.

Probably the reason that the study of cellular automata (CA) had to wait until the advent of the modern computer is simply that, before then, no one thought to look for them. They can certainly be constructed with little difficulty by hand on regular graph paper - as you will see. But the modern computer certainly enables one to more-easily and efficiently explore the universe of CA's - you will see that too.

What is a Cellular Automaton?

A cellular automaton (CA) consists of a (usually) rectangular grid of cells which can take on two (or more) different states (like "On" and "Off", or "Living" and "Dead") by following a small set of simple rules. Starting with a (usually) simple initial pattern, we observe what happens to the pattern in successive "generations" as it "evolves" according to its rules.

¹ These pages are intended as a "Cellular Automata for Dummies", by a dummy. None of the ideas presented in these pages are original with me. As I have worked through these concepts, I have tried to develop an elementary introduction to cellular automata for my students. The credit goes to Stephen Wolfram, his book "A New Kind of Science" and the Mathematica software, John Conway, Martin Gardner, and countless others whose work I have run across in print or on the Web. (If you are one of those countless others and want credit on these pages- just let me know!)

last update November 21, 2009 by JL Stanbrough