Skip to Main content Skip to Navigation

On the computational power and super-turing capabilities of dynamical systems.

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 literature are actually able to simulate analog automata. From this result we deduce that many dynamical systems have intrinsically super-turing capabilities.
Document type :
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download
Contributor : Colette Orange Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:05:54 AM
Last modification on : Saturday, September 11, 2021 - 3:18:58 AM


Files produced by the author(s)


  • HAL Id : hal-02101773, version 1



Olivier Bournez, Michel Cosnard. On the computational power and super-turing capabilities of dynamical systems.. [Research Report] LIP RR-1995-30, Laboratoire de l'informatique du parallélisme. 1995, 2+38p. ⟨hal-02101773⟩



Les métriques sont temporairement indisponibles