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.

Homework Assignments

 

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.