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

Abstract : 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).
Document type :
Reports
Complete list of metadatas

Cited literature [34 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101790
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:06:21 AM
Last modification on : Wednesday, November 20, 2019 - 3:13:40 AM

File

RR1997-14.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101790, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

17

Files downloads

35