Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: Nested Structures in Cellular Automata
Speaker: Eric Rowland, Rutgers University
Date: Thursday, January 19, 2006 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Among one-dimensional cellular automata, one finds beautiful examples of global nested ("fractal") patterns; the 2-color nearest-neighbor rule numbers 60, 90, 105, 150 all generate global nested structures when begun from a single black cell. Additionally, some cellular automata exhibit local nested structures on one side. The notoriously intractable rule 30 is such an example -- less obvious and more interesting than its global counterparts. In general, rules with local nested structure are characterized by positional bijectivity in one of the rule components. That is, under certain natural conditions, these rules are reversible in time, so that it makes sense to talk about the infinite history of the automaton as well as its future.
We will prove a general theorem accounting for nested structure in a right bijective, k-color rule, and we will explore a new class of integer sequences suggested by these investigations. A computer will be on hand to show us nice pictures of what we are talking about.