On the Computability of Reachable and Invariant Sets

The computation of reachable and invariant sets of nonlinear dynamic and control systems are important problems of systems theory. In this paper we consider the computability of these sets using Turing machines to perform approximate computations. We use Weihrauch’s type-two theory of effectivity for computable analysis and topology, which provides a natural setting for performing computations on sets and maps. The main results are that the reachable set is lower-semicomputable, but upper-semicomputable only if it equals the chain-reachable set, whereas invariant sets are upper-semicomputable.