Erin Craig graduated in May 2009 from New College of Florida with an undergraduate degree in mathematics. Inspired by the beauty of both algebra and automata, she spent her final year at New College developing and studying an extension of rule 90 to 1D automata over non-Abelian groups. Also a student of contemporary ballet, Erin is particularly interested in work that marries mathematics and movement and explores how the two inform each other.
Project: Reducibility in String Substitution Systems
Computational reducibility in CAs will be studied—specifically, what about a CA makes it reducible (or not), through looking at examples of those that are reducible and those that are (likely) not reducible.
For example, the powers of 2 written in base 6 correspond to a cellular automaton that looks as though it is not reducible, though there is clearly an easy formula to compute any row. Similarly, additive rules with random initial conditions tend to look complex, yet their evolutions are simple to compute. This project will study what, if anything, these automata have in common. Algebraic properties of these update rules will be studied first. Can they be understood as homomorphisms? And if not, what properties do they satisfy?
Concurrently, the additive rules that are well understood will changed slightly and studied to see if they are still additive. An extension of rule 60 will be studied first, using the dihedral group, D2n, and its group operation in place of Z2 and addition. The dihedral group was chosen because it is almost Abelian. Moreover, because D2n is a semi-direct product of Zn and Z2, rule 60 over D2n retains much of the structure from rule 60 over Z2. Though this extension of rule 60 has much in common with the original rule 60, the extension seems considerably more complex.
Favorite Three-Color Cellular Automaton