Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

From biological systems and epidemiology to traffic flow and Turing machines, cellular automata have proven to be versatile models across many fields. Their simple, local update rules give rise to rich and complex global behavior. In this talk, we will study the image space of one-dimensional cellular automata. In particular, we select an update rule uniformly at random and ask for the probability that a given periodic configuration lies in the image of the corresponding global transition function. We address this using a connection to random deBruijn graphs, in which combinatorial techniques and the Chen-Stein method for Poisson convergence allow us to find upper and lower bounds on our probability of interest.