Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy. - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1997

Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy.

(1)
1

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).
Fichier principal
Vignette du fichier
RR1997-14.pdf (513.26 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

  • HAL Id : hal-02101790 , version 1

Citer

Olivier Bournez. Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy.. [Research Report] LIP 1997-14, Laboratoire de l'informatique du parallélisme. 1997, 2+49p. ⟨hal-02101790⟩
20 Consultations
139 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More