Swarthmore College Department of Computer Science

Talk by Brian Patterson, Iowa State University Department of Computer Science

Multi-Resolution Cellular Automata
Wednesday, February 9, 2011
SCI 264, 7:30 pm (refreshments at 7:15)

Abstract

This talk introduces the field of computable analysis and multi-resolution cellular automata (MRCA), a multi-resolution variant of cellular automata. Cells in an MRCA are allowed to ``fission'' one or more times during the course of execution. At any given time, the MRCA may thus be carrying out computations on a variety of spatial scales. Our main result so far uses the MRCA model to give a natural characterization of the computability of sets in Euclidean space, provided that their boundaries are computably nowhere dense. I will also briefly discuss a restriction of this model, in-place MRCA computability, that restricts all rules to referring only to their own prior state (i.e., not neighbor states) and show this restriction still allows for MRCA computing of regions bounded by rational lines.

I will conclude by examining areas of possible future work ranging from examining how limited resources restricts what an MRCA can compute to applications to top-down design for nanoscale self-assembly using DNA tiles.