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.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...