Abstract. Let S be the domain of attraction of a computable and asymptotically stable hyperbolic equilibrium point of the non-linear systemẋ = f (x). We show that the problem of determining S is computationally unsolvable. We also present an upper bound of the degree of unsolvability of this problem. One of the central objects of study in continuous dynamical systems is the domain of attraction of an asymptotically stable equilibrium point. Determining this domain is one of the most important problems in (Lyapunov) stability theory. In the late 1960's there was a surge of theoretical studies analyzing properties of such domains. In recent years much effort has been devoted to the development of numerical methods for the estimation of these domains, which has resulted in numerous numerical algorithms. In contrast, relatively little theoretical work on computability of these domains exists. In fact, it is not yet known whether or not domains of attraction of computable systems are computable. In this paper, we show that, despite the existence of various successful numerical estimations, the problem of determining domains of attraction is computationally unsolvable. We also present an upper bound of the degree of unsolvability of the problem by showing that the domains of attraction of computable systems are recursively enumerable. Speaking roughly, a set is computable if its image can be generated by a computer with arbitrary precision. For real computation, there are several non-equivalent models. [19] . The BSS model permits real numbers as input and uses infiniteprecision arithmetic, while the bit model operates on infinite sequences of bits and uses finite-precision arithmetic; that is, "bit approximations" to the output are computed with arbitrary precision if good "bit approximations" to the input are accessible. Since finite-precision is generally used in "practical computation," we use the bit model in this paper. Associated with the bit model is the Type-Two Theory of Effectivity (TTE) [19] . Received by the editors July 11, 2008, and, in
On the other hand, it is shown in REF that for C ∞ dynamical systems, basins of attraction of hyperbolic sinks can be non-computable.
COMPUTATIONAL UNSOLVABILITY OF DOMAINS OF ATTRACTION OF NONLINEAR SYSTEMS
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
Mathematics