Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy.
Résumé
We study the computational power of rational Piecewise Constant Derivative (PCD) systems. PCD systems are dynamical systems defined by a piecewise constant differential equation and can be considered as computational machines working on a continuous space with a continuous time. We prove that the languages recognized by rational PCD systems in dimension d=2k+3 (respectively: d=2k+4), k >= 0, in finite continuous time are precisely the languages of the omega ^k th (resp. omega ^k +1 th) level of the hyper-arithmetical hierarchy. Hence the reachability problem for rational PCD systems of dimension d=2k+3 (resp. d=2k+4), k >0 , is hyper-arithmetical and is Sigma_{omega ^k}-complete (resp. Sigma_{omega ^k +1}-complete).
Nous étudions la puissance de calcul des systèmes à dérivée constante par morceaux (systèmes PCD) à coefficients rationnels. Les systèmes PCD sont des systèmes dynamiques définis par une équation différentielle constante par morceaux. Ils peuvent être vus comme des modèles de calcul évoluant sur espace continu avec un temps continu. Nous prouvons que les langages reconnus par des systèmes PCD rationnels en dimension d=2k+3 (respectivement: d=2k+4), k >= 0, en temps continu fini sont précisément les langages du omega ^k ieme (resp. omega ^k+1 ieme) niveau de la hiérarchie hyper-arithmétique. Ainsi le problème de l'atteignabilité des systèmes PCD de dimension d=2k+3 (resp. d=2k+4), k >0 , est hyper-arithmétique et est Sigma_{omega ^k}-complet (resp. Sigma_{omega ^k+1}-complet).
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
Loading...