On the computational power and super-turing capabilities of dynamical systems. - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1995

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

Résumé

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.
Nous étudions la puissance de calcul et de simulation des systèmes dynamiques. Dans un premier temps, nous introduisons et comparons plusieurs notions de simulation entre systèmes discrets. Nous donnons un cadre général permettant de considérer les systèmes dynamiques comme des modèles de calcul. Nous définissons un nouveau modèle de calcul : le modèle des automates analogiques. Nous déterminons la puissance de calcul de ce modèle et prouvons qu'il possède des capacités super-Turing. Nous prouvons alors que des systèmes dynamiques très simples tirés de la littérature sont en fait capable de simuler les automates analogiques. De ces résultats, nous en déduisons que beaucoup des sytèmes dynamiques ont intrinsèquement des capacités super-Turing.
Fichier principal
Vignette du fichier
RR1995-30.pdf (376.13 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02101773 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101773 , version 1

Citer

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⟩
20 Consultations
46 Téléchargements

Partager

Gmail Facebook X LinkedIn More