**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".