Achilles and the tortoise climbing up the arithmetical hierarchy

In this paper we show how to construct for every set P of integers in the a rithmetical hierarchy a dynamical system H with piecewise-constant derivati ves such that deciding membership in P can be reduced to solving the reacha bility problem between two rational points for H. The ability of such appar ently simple dynamical systems, whose definition involves only rational par ameters, to "solve" highly unsolvable problems is closely related to Zeno's paradox, namely the ability to pack infinitely many discrete steps in a bo unded interval of time. (C) 1998 Academic Press.