Can I read Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy on EtoBox?

Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy by Olivier Bournez is a Computer Science article available to read on EtoBox.

What is Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy about?

In this paper, we characterize the computafional power of dynamical systems with piecewise constant derivatives (PCD) considered as computational machines working on a continuous real space with a continuous real time: we prove that piecewise constant derivative systems recognize precisely the languages of the okth (respectively (ok + 1)th) level of the hyper-arithmetical hierarchy in dimension d = 2k + 3 (respectively d = 2k + 4), k >O. Hence we prove that the reachability problem for PCD systems of dimension d = 2k + 3 (resp. d = 2k + 4), k 2 1, is hyper-arithmetical and is Cd-complete (resp. Cd+, -complete).

Who reads Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy?

Author

Olivier Bournez

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0304-3975)

Published

1999

Language

EN

Field

Computer Science (Physical Sciences)