Date: Wed 03 Jun
Time: 15.00
Place: room 214

Speaker: Howard Blair (Syracuse Univ.)
Title: Continualizing State Transition Systems
Reference: Maurizio Martelli

Abstract. Computation takes place in a space and is local. There is no action at a distance. Turing machines realize this notion in an excessively restricted way since computation is limited to be happening at only one place in the space at a time. Cellular automata (CA) provide a more powerful realization since computational activity can occur all over the space simultaneously. Familiar models of computation such as Turing machines, as well as some formal systems, such as certain first-order theories that present no loss of generality, are CA's. A CA is a symbolic dynamical system. Computation is discrete with respect to both time and local components of state. But discrete processes may sometimes usefully be seen as traces, or projections, of continuous processes. We represent discrete processes as orbits in symbolic dynamical systems. A dynamical system is symbolic if time as well as local components of the states of the system are discrete, discrete if time is discrete, and continuous if both time as well as local components of the state are continuous. A symbolic dynamical system D is continualized by a dynamical system C if every state of D is a state of C, every orbit in C that starts from a state of D is an orbit in D (when, if necessary, sampled at appropriate discrete times), and the orbits of D are attractors of orbits of C. In this talk we will give a simple constraint under which continualizations of CA's exist and are unique. The utility of continualization will be illustrated by a number of examples, including: a heuristic algorithm for satisfiability based on gradient descent; a probabilistic heuristic for generating satisfying valuations of propositions based on Newton's method; continualization of arbitrary graphical data structures; and continuous tuning of CA's to exhibit complex self-organizing behavior by exploiting a precisely defined notion of "edge of chaos".