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 omega(k)th (respectively (omega(k) + 1)th) level of the hyper-arithmetical hierarchy in dimension d = 2k + 3 (respectively d = 2k + 4), k greater than or equal to 0. Hence we prove that the reachability problem for PCD systems of dimension d = 2k + 3 (resp. d = 2k + 4), k greater than or equal to 1, is hyper-arithmetical and is Sigma(omega k)-complete (resp. Sigma(omega k+1)-complete). (C) 1999-Elsevier Science B.V. All rights reserved.