Achilles and the Tortoise Climbing Up the Arithmetical Hierarchy

摘要

In this paper we show how to construct for every setPof integers in the arithmetical hierarchy a dynamical system H with piecewise-constant derivatives such that deciding membership inPcan be reduced to solving the reachability problem between two rational points for H. The ability of such apparently simple dynamical systems, whose definition involves onlyrationalparameters, to “solve” highly unsolvable problems is closely related to Zeno's paradox, namely the ability to pack infinitely many discrete steps in a bounded interval of time.