Bio

Lydia Chilton was born March 26, 1984. She is currently an undergraduate student at MIT majoring in Pure Mathematics and Economics. She’s interested in NKS-related work with Simple Programs, elementary Cellular Automata, and circle packing. Her research so far with NKS has focused on pure NKS and explaining simple program behavior.

Project: N-Tuples in Elementary 1-Dimensional Cellular Automata

An N-Tuples is a row of cells of length N. I speculated that it would be relevant to investigate which of the 256 rules could produce all possible N-Tuples for a given N. E.g. Rule 110 can produce all rows or length 1,2,3 and 4 which contain all the possible combinations of black and white cells. It cannot, however, produce all rows of length 5. I was able to prove, based on neighbor dependency, that 30 of the 256 rules are capable of producing all N-Tuples of any length. That group had a strong overlap with the Class 3 rules (rules which produce random behavior from random initial conditions), and a likely explanation for random behavior could be to say that rules capable of producing all possible N-Tuples of any length will produced randomness. This however, excluded 8 Class 3 rules which are missing tuples. After investigation, I determined that those 8 all had the capability of emulating rule 90 (a rule capable of producing all possible N-tuples) or emulating a rule that emulates rule 90 using blocks with length less than 8 to emulate one block of rule 90. That allowed me to conclude that rules capable of producing all N-Tuples non-trivially and those that emulate rule 90 are the Class 3 rules for the Elementary 1-D Cellular Automata.

Favorite Three-Color Cellular Automaton

Rule Chosen: 34988764

Reason: I am accustomed to seeing randomness such as in rule 30 with order on one edge and randomness on the other. This rule however, has order on either side that merges into disorder somewhere many steps later. Such behavior is not possible in 2 color CA’s and I wonder what mechanics make it possible in the 3 color CA and what other phenomenon may or MAY NOT be possible. Answering the question of what occurances are forbidden now occurs to me to be important to ask when you have as much variety as you have available with 7 billion different rules.