Cellular Automata: Complex Patterns from Simple Rules

David Eppstein, University Studies 3, Spring 2007

Cellular automata such as Conway's famous "Game of Life" are systems for describing complex and changing visual patterns based on very simple computational rules. In this seminar, we'll see the kinds of patterns that can be generated with cellular automata, find out about computer programs for exploring cellular automaton rules, and learn about how these systems can model phenomena from the physical world.

The course will meet Mondays, 11:00 - 11:50, in CS 360D. Grading will be attendance-based.

Tentative Schedule of Topics:

• Week 1. Introduction: pretty patterns from simple rules. Primordial soup kitchen galleries: 1, 2. Cyclic cellular automata.
• Week 2. Conway's Game of Life. See Alan Hensel's Life applet or Golly for many interesting patterns in this system.
• Week 3. Life-like rules and Wolfram's classification.
• Week 4. One-dimensional cellular automata, traffic modeling, rule 184, and ballistic annihilation.
• Week 5. Von Neumann's theory of self-reproducing automata, additive rules, Sierpinski triangles, and rules with simple replicators.
• Week 6. Wireworld, circuit simulation, and Life circuitry
• Week 7. Reversible cellular automata. The paradox of locally time-symmetric dynamics leading to a global increase of entropy over time. Pool ball dynamics and CA simulations of pool balls. Reversible CA construction techniques: 2nd order CA and block-partitioning CA. Simulated diffusion. The search for the Garden of Eden.
• Week 8. Rule 110
• Week 9. No class (Memorial day holiday)
• Week 10. Course evaluations