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 :
Reports
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101773
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:05:54 AM
Last modification on : Wednesday, November 20, 2019 - 2:51:14 AM

File

RR1995-30.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101773, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

13

Files downloads

11