Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy

In this paper, we characterize the computational 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 ! k th (respectively: ! k + 1 th ) level of the hyper-arithmetical hierarchy in dimension d = 2k + 3 (respectively: d = 2k + 4), k 0. Hence we prove that the reachability problem for PCD systems of dimension d = 2k + 3 (resp. d = 2k + 4), k 1, is hyper-arithmetical and is \Sigma ! k -complete (resp. \Sigma ! k +1 -complete). 1 Introduction There has been recently an increasing interest in the fields of control theory and computer science about hybrid systems. A hybrid system is a system that combines discrete and continuous dynamics. Several models have been proposed in literature. In particular, in [2, 3, 4], the authors introduce Piecewise Constant Derivative systems ..