A New Computational Model: Continuous Time

[Hava Siegelmann]

Dear friends:

I wish to introduce you to a new work in continuous-time computability
that may be of interest to some of you.


 
        Analog Computing and Dynamical Systems
        ======================================
Hava T. Siegelmann         and             Shmuel Fishman
          Technion --- Israel Institute of Technology 
iehava at ie.technion.ac.il      fishman at physics.technion.ac.il


                  ABSTRACT
               
This work is aimed to gain an enlarged and deeper understanding of the
computation processes possible in natural and artificial systems.  We
introduce an interface between dynamical systems and computational
models. The theory that is developed encompasses discrete and
continuous analog computation by means of difference and differential
equations, respectively. Our complexity theory for continuous time
systems is very natural and requires no external clocks or
synchronizing elements.

As opposed to previous models we do not apply some nature principles
to the Turing model but rather start from realizable and possibly
chaotic dynamical systems and interpret their evolution as generalized
computation.  By applying the basic computational terms such as,
halting, computation under resource constraints, nondeterministic and
stochastic behavior to dynamical systems, a general, continuous-time
computational theory is introduced. The new theory is indeed different
from the classical one: in some ways it seems stronger but it still
has natural limits of decidability.


=====================================================================

Let me shortly explain why I suspect that this theoretical
computer-science work may be of interest to the Connectionist:

1. In some way, this is a generalization of the Hopfield network. The
   meaningful attractors of these networks --- where information is
   stored --- are all simple: either stable
   fixed points or limit cycles, that are periodic orbits.
   As most dissipative dynamical systems converge to chaotic
   attractors, the Hopfield network is indeed a very special case of
   recurrent networks.

   In our new work, we present the foundations of computation for
   dissipative dynamical systems; the attractors can be of any kind.
   In spite of this variety, the computation and computation times in
   dynamical are now defined in unified, natural, and unambiguous
   mathematical terms.


2. There is another reason, but here it really depends on personal
   belief. Previously, the CS theoreticians of us considered
   functions, trajectories, and control as a discrete time
   process. Looking at it without this discretization seems to enlarge
   our understanding of continuous time computation, with no need for
   external clocks or all other related discretization tricks. I do
   not understand enough in biological control to state more than that
   careful comments I would love to hear from those of you that
   understand if indeed you see any possible application to your kind
   of work.


                      Best regards,


                           Hava Siegelmann
                             Technion
                              Israel