|
NeuroCOLT
Technical Report NC-TR-96-005
On the computational
power and super-Turing capabilities of dynamical systems
Olivier
Bournez
Department LIP
ENS-Lyon
France
Michel
Cosnard
Department LIP
ENS-Lyon
France
Abstract
We explore the simulation and computational capabilities of dynamical
systems. We first introduce and compare several notions of simulation
between discrete systems. We give a general framework that allows
dynamical systems to be considered as computational machines. We introduce
a new discrete model of computation: the analog automaton model. We
determine the computational power of this model and prove that it
does have super-Turing capabilities. We then prove that many very
simple dynamical systems from the literature are actually able to
simulate analog automata. From this result we deduce that many
dynamical systems have intrinsically super-Turing capabilities.
Download Compressed
Postscript
Title
page
|