Aleksandra Portnova

Cellular Automata and the "Edge of Chaos"

ABSTRACT: Cellular automaton (CA) is a set of finite state machines ("cells") in some initial state, where the next state depends on their own state and states of several of their neighbors in a way specified by the rules. Rules for CAs capable of complex computations are found around the "edge of chaos." The phenomenon of "edge of chaos" is a phase transition between ordered and chaotic behavior of CAs. The talk will discuss dynamical properties of CAs capable of global computation, in particular the results of an experiment by M. Mitchell, J. Crutchfield, and P. Hraber that dealt with identifying the "edge of chaos."

ABSTRACT: If we say that two actors are linked if they have appeared in a movie together, then the Kevin Bacon Problem states that every actor is connected to Kevin Bacon through a chain of at most six links. This is known as a small world phenomenon and popularized as "six degrees of separation". This talk will discuss a survey conducted at St. Lawrence University to determine the degrees of separation of the senior class at St. Lawrence. The results of the survey are analyzed using graph theory related to social networks. The theoretical techniques and the results will be presented in this talk.