On the computational power of dynamical systems and hybrid systems

被引:34
作者
Bournez, O [1 ]
Cosnard, M [1 ]
机构
[1] ECOLE NORMALE SUPER LYON,LAB INFORMAT PARALLELISME,F-69364 LYON 07,FRANCE
关键词
D O I
10.1016/S0304-3975(96)00086-2
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We explore the simulation and computational capabilities of discrete and continuous dynamical systems. We introduce and compare several notions of simulation between discrete and continuous systems. We give a general framework that allows discrete and continuous dynamical systems to be considered as computational machines. We introduce a new discrete model of computation: the analog automaton model. We characterize the computational power of this model as P/poly in polynomial time and as unbounded in exponential time. We prove that many very simple dynamical systems from literature are able to simulate analog automata. From these results we deduce that many dynamical systems have intrinsically super-Turing capabilities.
引用
收藏
页码:417 / 459
页数:43
相关论文
共 28 条