Cellular Automata and Complexity, CS 470
We will use the beautiful behavior of cellular automata (CA) to explore theories of computation and complexity. CA are lattices of cells that interact through simple rules -- crazy simple rules. Each cell has a value of 0 or 1, and the cells update their number based on their neighbors' values. A typical update rule is "sum modulo 2". That's it.
But even with these simple rules, we'll show that CA can model complex physics like fluid flow, social interactions like rioting, and biological behaviors like herding. Even more profound, we'll prove that some CA are capable of "universal computation". In other words, despite their simple rules, some CA can mimic the computer on your desk and are every bit as powerful!
At a purely aesthetic level, CA produce beautiful and mesmerizing patterns reminiscent of Escher gone mad. Fractals describe many of these intricate designs, and group theory can explain their structure, but you may find yourself drawn and inspired by their artistic potential.
This is a junior/senior level class, though there are few pre-requisites. We will do some full-on, no-holds-barred, math proofs, so linear algebra would be helpful. We will also do some basic programming. The more advanced your mathematics and programming skills, the more you will get out of the class.
Download the Cellular Automata Explorer (it's free!)
Syllabus (please read)
Class Notes Part 0: Preface and CA Philosophy
Class Notes Part 1: Experimenting with CA
Class Notes Part 2: Introduction to CA
Class Notes Part 3: 1-d CA and Cycle Lengths
Class Notes Part 4: Rule 102 and Proofs
Class Notes Part 5: Other Approaches to Rule 102
Class Notes Part 6: Proofs for Rule of Your Choice
Class Notes Part 7: Other Types of CA (Totalistic, etc.)
Class Notes Part 8: Write Your Own CA Rule!
Class Notes Part 9: CA Explorer Architecture (...and some of the UML)
Class Notes Part 10: Behavioral Classification (I, II, III, IV)
Class Notes Part 11: Utility of CA Classes
Class Notes Part 12: Class Hierarchy and Phase Transitions
Class Notes Part 13: CA and Turing Machines
Class Notes Part 14: Life is Universal (Proof)
Class Notes Part 15: Other CA Are Universal
Class Notes Part 16: Applications in Physics
Class Notes Part 17: Applications to Social Systems
Related links for social applications:
Bahr et al, 2009, Exploiting Social networks to Mitigate the Obesity Epidemic and supplementary material
Bahr and Passerini, 1998, Statistical Mechanics of Opinion Formation: Micro-sociology.
Bahr and Passerini, 1998, Statistical Mechanics of Collective Behavior: Macro-sociology.
Bahr and Bekoff, 1999, Predicting Bird Flock Vigilance with Cellular Automata.