SCS Undergraduate Thesis Topics

2007-2008
Kevin McInerney Klaus Sutner Discovering Tractable Cellular Automata Questions
     

Cellular automata(CA) are a powerful computational device. CA's are interesting in that computation on a CA is both local and massively parallel. Moreover, even for complex, Turing-complete CA's the rule set is small and easily implementable on hardware. Using prepositional logic with the "steps to" relation, we can ask rather complex questions about the CA state space, such as: "Is this CA reversable?" "Does this CA have a three cycle?" "Is this CA surjective?" We can represent the steps to and inequality relations as finite state machines over infinite words, and use simple algorithms to combine these FSMs into larger FSMs that represent general prepositional statements. However, combining these FSMs can cause them to grow exponentially (specifically, to negate a machine, we must first determinize it, which expands the machine by an exponential in the worst case.) The goal of this thesis is to catalog the prepositional statements about FSMs that are tractably answer!


Close this window