I just finished my thesis about cellular automata. Specifically, I worked on the automatic verification of logical formulas about the behavior of a given automaton.
Here's what that means. Suppose that you have some cellular automaton p, and you're interested in knowing whether p returns to its original state when you run it for a while. For finite grids and specific opening patterns this is an easy question to answer -- in theory -- you just simulate the automaton for long enough. But what about infinite grids? Or what if we wanted to answer a question like "does there exist a configuration of p which returns to its original state after 3 steps?" Or what if the automaton is just too big and too complicated to simulate for a long period of time? The majority of my work was in implementing a way of answering questions such as these (link for the really, really interested reader: http://carnegie-mellon.academia.edu/documents/0107/1998/thes...).
Cellular automata are surprisingly deep, for how simple they are. However, they aren't "a new kind of science" - like most constructs in computer science they are amenable to mathematical treatment.
If you already know a fair amount about CA, here's another good question for you to think about. How can we better classify different types of cellular automata based on their behavior? The usual classification system essentially boils down to choosing one of "it is obvious what this CA does", "you can prove what it does", "you can sort of guess what it does", and "no one has any idea so maybe this is universal". This is clearly unsatisfactory -- any suggestions?
Here's what that means. Suppose that you have some cellular automaton p, and you're interested in knowing whether p returns to its original state when you run it for a while. For finite grids and specific opening patterns this is an easy question to answer -- in theory -- you just simulate the automaton for long enough. But what about infinite grids? Or what if we wanted to answer a question like "does there exist a configuration of p which returns to its original state after 3 steps?" Or what if the automaton is just too big and too complicated to simulate for a long period of time? The majority of my work was in implementing a way of answering questions such as these (link for the really, really interested reader: http://carnegie-mellon.academia.edu/documents/0107/1998/thes...).
Cellular automata are surprisingly deep, for how simple they are. However, they aren't "a new kind of science" - like most constructs in computer science they are amenable to mathematical treatment.
If you already know a fair amount about CA, here's another good question for you to think about. How can we better classify different types of cellular automata based on their behavior? The usual classification system essentially boils down to choosing one of "it is obvious what this CA does", "you can prove what it does", "you can sort of guess what it does", and "no one has any idea so maybe this is universal". This is clearly unsatisfactory -- any suggestions?