Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space

A large number of problems in a diverse range of areas, such as program verification [31], numerical analysis [40, 35], economics [4], probabilistic systems [1, 6], and biology [45, 24] reduce to a problem of the following type: Given a set $A\subseteq X$, a function $f:X\to X$, and a point $x_0\in A$, decide whether $x_0$ escapes $A$ under finitely many iterations of $f$.

Unsurprisingly, the study of automated methods for the solution of such problems has received much attention [41, 43, 29, 28, 30, 27, 21, 36, 37, 19, 16, 5, 20].

Existing work on automated decision methods largely focusses on linear systems. In fact, the scope of automated decision methods for non-linear systems appears to be quite limited: the above problem is undecidable [42] already when $f:{ℝ}^d\to {ℝ}^d$ is a piecewise linear function and $A$ is a polyhedron in ${ℝ}^d$.

All of the aforementioned results assume that the system is specified exactly, by means of rational or algebraic numbers. In application areas such as engineering and the natural sciences, it may be unrealistic to assume that the system under consideration is known to perfect accuracy. Rather, one should assume that the system is known only up to some (presumably small) error with respect to a given distance function. In this context, one is arguably less interested in deciding the problem for a single given instance, but to exhibit a neighbourhood of the given instance for which the answer to the problem remains constant – provided that such a neighbourhood exists. If the given instance lies on a “decision boundary”, i.e., the answer to the problem is sensitive to arbitrarily small perturbations of the instance, not much appears to be gained by solving the problem for that specific instance. In some sense, this can also be viewed as an opportunity to increase the scope of automated decision methods, since the aforementioned undecidability results usually occur due to instances that lie on such decision boundaries.

This has led to various problems of this type being studied in various, generally non-equivalent, formalisations of “robust decidability” [25, 2, 38, 14, 3].

The aim of this paper is to demonstrate by means of a case study that computable analysis constitutes a very suitable framework for the study of robust decidability questions. Computable analysis is the study of computation on data that is not specified by a complete finite description, but rather given as an infinite sequence of increasingly accurate approximations. For example, a real number $x\in ℝ$ can be encoded by an infinite sequence ${(I_n)}_n$ of nested intervals with rational endpoints such that $\{x\}={\bigcap }_{n\in \mathbb{N}}{I}_n$. An algorithm for computing a real number $x\in ℝ$ takes as input a non-negative integer $n\in \mathbb{N}$ and outputs an interval $I_n$ with rational endpoints. The algorithm is required to ensure that the sequence ${(I_n)}_n$ is nested and satisfies $\{x\}={\bigcap }_{n\in \mathbb{N}}{I}_n$. An algorithm for computing a real function $f:ℝ\to ℝ$ takes as input an infinite sequence of intervals ${(I_m)}_m$ which is guaranteed to encode a real number $x\in ℝ$, and returns as output an infinite sequence of intervals ${(J_n)}_n$. The algorithm is required to ensure that for all input sequences ${(I_m)}_m$ encoding a real number $x$, the output sequence ${(J_n)}_n$ encodes the real number $f(x)$. The infinite sequence ${(I_m)}_m$ is presented to the algorithm as a “black box”: the algorithm can query the black box for any integer $m\in \mathbb{N}$ to receive the interval $I_m$. Formally, this idea can be realised by using oracle Turing machines with an “input oracle” [22] or, equivalently, by using Turing machines with an infinite read-only tape that contains the entire infinite input sequence [44]. It is important to observe that in the definition above, an algorithm for computing a real function operates on all real numbers, not just on computable ones. This should be contrasted with Markov computability [23, 18], where algorithms operate only on computable objects which are presented as indexes of Turing machines that compute the objects.

One may object that the above model of computation is still unrealistic: Our initial motivation – to study systems that are not known exactly – suggests to consider decision methods for objects that are known only to some fixed finite precision. While in computable analysis objects are not given by an infinitely precise finite description, they can still be approximated to arbitrary, rather than fixed, finite precision. However, an algorithm that computes a function from one space to another can be automatically lifted to one that computes the range of the function over any given compact subset of the space [32, Proposition 11], automatically yielding an effective method for operating on objects that are known only to some fixed precision. See also [25, Section 2] for a discussion of this in the context of decision problems.

We study the following very general instantiation of the decision problem mentioned above: Given a continuous function $f:{ℝ}^d\to {ℝ}^d$, a closed set $A\subseteq {ℝ}^d$, and a point $x_0\in A$, determine whether the point escapes $A$ under iteration of $f$. To make this precise, we introduce standard encodings of points, sets, and functions, which we discuss in detail in Section 2.3. Here, the point escapes if and only if there exists $n\in \mathbb{N}$ such that $f^n(x_0)\notin A$ – i.e., the point is said to escape if it leaves the set after some number of function applications, even if it re-enters the set after further applications of $f$. We will refer to this problem as the Point Escape Problem.

Since the inputs to an algorithm are given as infinite sequences of increasingly accurate approximations, there is no hope to obtain a correct algorithm that halts on every input for any non-trivial problem of the above type: every computable function must be continuous, and every continuous function from a connected space to a two-point space is constant. Since no total algorithm exists for deciding the problem in question, the next best alternative is to ask for a partial algorithm that halts on as many problem instances as possible. Accordingly, we will call a partial algorithm for deciding a problem complete if its halting set contains the halting set of all correct partial algorithms deciding the same problem. This is equivalent to asking that the algorithm halt on all problem instances whose answer is stable under small perturbations. See Section 2.2 for a more formal discussion and [25, Proposition 2.1] for a proof of this equivalence. Observe that for discrete spaces such as the natural numbers, an algorithm is complete in this sense if and only if it halts on all inputs, so that the above definition of completeness is a generalisation of the usual definition in classical computability.

Our algorithm for solving the Point Escape Problem is rather straightforward: We keep track of an overapproximation $O$ of a finite initial segment $\{x_0,f(x_0),\mathrm{\dots },f^N(x_0)\}$ of the orbit, as well as of overapproximations $Q_i$ of the individual points $\left\{f^i(x_0)\right\}$ in the orbit. If we witness that $Q_i$ is separated from the closed set $A$, then we conclude that $x_0$ escapes under $f$. If we witness that $O$ is included in the interior of $A$ and we can find an overapproximation $O^{\prime }$ of the image $f(O)$ with $O^{\prime }\subseteq O$, then we conclude that the point $x_0$ must be trapped. If the overapproximations we have computed do not allow us to draw either conclusion, we compute more accurate overapproximations to longer initial segments of the orbit, until we are able to make a decision.

Our main contribution is to show that this simple algorithm is complete in the above sense. The key idea is to show that the search for an invariant set for $f$ is guaranteed to terminate provided that $f$ has a robust invariant whose interior contains $f(x_0)$. A compact set $V\subseteq {ℝ}^d$ is called a robust invariant for $f$ if $f(V)\subseteq V^{\circ }$, where $V^{\circ }$ denotes the interior of $V$. We show that if $x_0$ is trapped but $f(x_0)$ is not contained in a robust invariant, then $x_0$ escapes under arbitrarily small perturbations of $f$ and $A$.

We will further show that if $x_0$ is trapped but $f(x_0)$ is not contained in a robust invariant and $A\ne {ℝ}^d$, then $x_0$ escapes $A$ under arbitrarily small perturbations of $f$ alone, with $A$ being fixed. This implies that our algorithm, which takes $x_0$ and $A$ as inputs, is complete for all fixed $x_0$ and $A⊊{ℝ}^d$, when only the function $f$ is given as an input. Thus, a bespoke algorithm for fixed special sets or initial points, say $x_0=0$ or $A={[0,1]}^d$ will not halt on more functions than our general algorithm.

Since a complete algorithm is only required to halt on robust instances, one is lead to the problem of determining the “size” of the robust instances. In the worst case, a problem may not have any robust instances at all, so that a complete decision method is given by the algorithm that never halts. We show that the halting set of our algorithm is “large”, in the sense that the algorithm halts on a dense set of inputs and that the set of trapped problem instances is the closure of its interior.

Finally, which problem instances are robust depends on the class of functions and how these functions are represented (by our aforementioned result it surprisingly does not essentially depend on how the sets or initial points are represented). We allow arbitrary continuous functions as inputs, given by the weakest representation that makes function evaluation uniformly computable.

In general, if the problem is restricted to a smaller class of functions, potentially with a representation that induces a stronger topology, then previously non-robust instances may become robust, so that our algorithm will in general fail to be complete for restrictions of the Point Escape Problem to smaller function classes.

Indeed, The topology induced by our representation of continuous functions is the topology of uniform convergence on compact sets. In this topology, every neighbourhood of a function $f$ contains functions $g$ that agree with $f$ on some compact set, but differ arbitrarily from $f$ outside this compact set. For this reason, our algorithm will fail to halt on very simple-looking problem instances where the given set is unbounded. Consider for example the problem instance $(A,f,x_0)$ consisting of the set $A=\{x\in ℝ\mid x\ge 0\}$, the function $f(x)=2x$, and the initial point $x_0=1$. Since $f$ does not map any compact set into its interior, our algorithm will fail to halt on this problem instance.

However, we will show that systems such as the above can be effectively treated by our algorithm after first applying a suitable compactification. More specifically, we show that the problem of deciding whether a point escapes a polyhedron (which is in general unbounded) under an affine linear map reduces to the Point Escape Problem for continuous functions in such a way that robust problem instances get mapped to robust problem instances. We conjecture that this reduction extends to more general non-linear systems that are sufficiently well behaved “at infinity”.

To discuss the applicability of our algorithm to a class of much more rigid non-linear systems, we consider the problem of deciding whether the origin in the complex plane has an unbounded orbit under a quadratic polynomial, represented by a single complex parameter. The existence of a complete algorithm for this problem is closely related to the computability of the Mandelbrot set [17]. We give a reduction of this problem to the Point Escape Problem that maps robust instances to robust instances if and only if the hyperbolicity conjecture holds true.

The rest of the paper is structured as follows: in Section 2 we review the relevant background material from computable analysis, discuss completeness of decision methods over continuous data, and formally introduce our representations of points, sets, and functions. Section 3 contains a formal description of our main algorithm and our main results: that the algorithm is correct, complete, and generically terminating. In Sections 4 and 5 we describe our applications to linear and quadratic systems respectively.

We will now present our algorithm for maximally partially deciding whether a point escapes a closed set under the iteration of a continuous function. More precisely, we consider the following decision problem:

Algorithm 1 above takes as input a name ${(F_n)}_n$ of a continuous function $f:{ℝ}^d\to {ℝ}^d$, a name ${(I_n^A,E_n^A)}_n$ of a closed set $A\subseteq {ℝ}^d$, and a name ${(X_n)}_n$ of a point $x_0\in A$. It either runs forever or halts within finitely many steps. Upon halting, it reports whether there exists $n\in \mathbb{N}$ such that $f^n(x_0)\notin A$. The algorithm proceeds in stages, working on a subdivision of ${[-2^n,2^n]}^d$ into cubes of side-length $2^{-n}$ in each stage. The stages are described in Algorithm 2. At each stage, Algorithm 2 computes an overapproximation of the orbit of $x_0$ to determine whether $x_0$ escapes. At the same time, it searches for an invariant set under $F_n$ which is contained in $A^{\circ }$, yielding an invariant set under $f$ which is contained in $A^{\circ }$.

It is straightforward to verify that Algorithm 1 is correct, i.e., that it produces the correct answer upon halting.

As mentioned in the introduction, Algorithm 1 may fail to terminate on very simple-looking problem instances when $A$ is not a compact set. The main reason for this is that our representation of continuous functions induces the topology of uniform convergence on compact sets, or equivalently, the topology induced by the metric (1). In order for two functions $f,g:{ℝ}^d\to {ℝ}^d$ to have distance at most $2^{-n}$, it suffices that $f$ and $g$ agree on the cube ${[-2^{n+1},2^{n+1}]}^d$, potentially admitting function values of arbitrarily large distance outside of this cube. Thus, every function $f$ has “arbitrarily small” perturbations that differ from $f$ arbitrarily outside a certain bounded set.

Revisiting the example from the introduction, consider the set $A=\{x\in ℝ\mid x\ge 0\}$, the initial point $x_0=1\in A$, and the map $f:ℝ\to ℝ$, $f(x)=2x$. It is clear that the point $x_0$ is trapped in $A$ under iteration of $f$. However, it cannot be robustly trapped, since $f$ does not admit any robust invariants. More explicitly, with respect to the metric (1), $f$ is the limit of the sequence

We have $f_n^n(1)=2^n$ and $f_n(2^n)=-1$, so that $x_0$ escapes $A$ under each $f_n$.

While a naïve direct application of Algorithm 1 fails to verify that the system is trapped, we can exploit the fact that the particular $f$ and $A$ given above are well behaved “near infinity” to compute a compactified version of the system that is amenable to analysis via Algorithm 1.

Consider the map $\mathrm{\Phi }:ℝ\to (-1,1),\mathrm{\Phi }(x)=\frac{x}{1+|x|}$. This map has a continuous inverse, explicitly given by ${\mathrm{\Phi }}^{-1}:(-1,1)\to ℝ,{\mathrm{\Phi }}^{-1}(x)=\frac{x}{1-|x|}$. We have $\mathrm{\Phi }\circ f\circ {\mathrm{\Phi }}^{-1}(x)=\frac{2x}{1+|x|}$. The expression on the right-hand side of this equality defines a total function $\overline{f}(x):ℝ\to ℝ$. Observe that a point $x$ is trapped in $A$ under $f$ if and only if $\mathrm{\Phi }(x)$ is trapped in $A$ under $\overline{f}$. The latter can be verified by Algorithm 1 for all $x>0$, since $\overline{f}$ admits the robust invariant $[\frac{\mathrm{\Phi }(x)}{2},2]$ with $\mathrm{\Phi }(x)\in (\frac{\mathrm{\Phi }(x)}{2},2)\subseteq [\frac{\mathrm{\Phi }(x)}{2},2]\subseteq A^{\circ }$.

To further illustrate how the scope of Algorithm 1 can be extended using this compactification technique, we generalise the above observation to give a solution for the problem of deciding whether a point escapes a polyhedron (which is in general unbounded) under the iteration of an affine linear map:

We will give a reduction of the Linear Escape Problem to the Point Escape Problem that sends robust instances to robust instances based on the compactification idea discussed above.

Before we describe the reduction, we classify the robust instances of the Linear Escape Problem. Since all escaping instances are robust, we focus only on trapped instances.

For a matrix $A$, let $\sigma (A){\subseteq }_{\text{fin}}ℂ$ denote the set of its eigenvalues and $r(A)=\max \left\{|\lambda |\mid \lambda \in \sigma (A)\right\}$ denote the largest value among the absolute values of its eigenvalues.

For a polyhedron $P={\bigcap }_{i=1}^m{H}_i$ with $H_i=\{x\in {ℝ}^d\mid N_{i}x\le D\}$, we let $P_0={\bigcap }_{i=1}^m{H}_i^0$, where $H_i^0=\{x\in {ℝ}^d\mid N_{i}x\le 0\}$.