Reachability problems in low-dimensional iterative maps

Reachability problems in low-dimensional iterative maps Oleksiy Kurganskyy1, Igor Potapov2, and Fernando Sancho Caparrini3 1Institute of Applied Mathematics and Mechanics, Ukrainian National Academy of Sciences, 74 R. Luxemburg St, Donetsk, Ukraine, [email protected] 2Department of Computer Science, University of Liverpool, Chadwick Building, Peach St, Liverpool L69 7ZF, U.K., [email protected] 3Department of Computer Science and Artificial Intelligence, University of Seville, Spain, [email protected] Abstract. In this paper we analyse the dynamics of one-dimensional piecewise maps (PAMs). We show that one-dimensional PAMs are equivalent to pseudo-billiard or so called “strange billiard” systems. We also show that the more general class of rational functions leads to undecidability of reachability problem for one-dimensional piecewise maps with a finite number of intervals. Keywords: Theory of computing, iterative piecewise maps, pseudo-billiard systems, universality 1 Introduction In the present work we investigate a class of hybrid systems defined by onedimensional piecewise maps. We are mainly interested in a class of one-dimensional piecewise-affine maps (PAMS) [2]. The analysis of piecewise-affine maps is one of the simplest model that generate complex behaviour, see [2–4, 6, 7]. It is known that the reachability problem is undecidable for the two-dimensional case and it is open for dimension one [1, 2]. It was recently shown that PAM is equivalent to hierarchical piecewise constant derivatives system (HPCD)[2]. In this paper we show that PAM is also equivalent to planar pseudo-billiard systems (PBSs) or so called “strange billiards” model that is a well known object in bifurcation and chaos theory [10, 11]. In contrast to HPCD which is a hybrid automaton where each state is defined by planar piecewise constant derivatives system (PCD), the model of PBS can also be seen as two dimensional linear hybrid automaton but with only one state. Although the reachability for PAMs is known to be open we think that the shown equivalence between PBSs and PAMs can be useful and the results from chaos theory about “strange billiards” [10, 5, 11] could help understand the complexity in one-dimensional piecewise-affine maps. In the second part of this paper we are exploring the complexity of more general class of rational maps that includes affine maps. It was shown in [8] that piecewise iterative maps defined by a very restricted basis of elementary functions: {x2, x3,2 √x, 3 √x, x ±1,10 ·x} can simulate a Minsky machine even in dimension one. Comparing to [8], we found a new way how to create a copy of information for a temporal use in dimension one. We show that it is possible to avoid square root and cube root functions using only rational functions. However in the current construction two of the finite number of intervals we define are infinite. As a main result in this part we show how to simulate (in direct way) a Minsky machine in one-dimensional piecewise rational maps (PRM) of degree 2. From it follows that the reachability problem for PRM is undecidable. It would be interesting to investigate a natural class of one-dimensional piecewise linear rational maps that is in between affine and rational maps. The main motivation for this class of systems is based on the fact that the reachability in one-dimensional piecewise linear rational maps can be seen as parameterized reachability in two dimensional linear4maps. Another interesting question is nondeterministic maps where transformations can be applied in any order. In this case reachability problems for nondeterministic linear rational maps corresponds to parametrized membership in 2 ×2 matrix semigroups. According to undecidability in PRM we think that it is also very likely to find undecidability of reachability problems in a nondeterministic version of one-dimensional rational maps. 2 Preliminaries In what follows we use traditional denotations N,Qand Rfor the sets of naturals, rationals and reals respectively. A function from a set Ato a set B, we will denote by f:A→B. If fis an injection such that dom(f) = A, then it will be denoted by f:A ,→B. In some cases we put x7→ yunder the definition of a function fto express that y=f(x), for example: f:R→R x7→ ax +b is a way to say that f(x) = ax +b. If we have a set Ain a topological space (usually we will consider Ror R2 with the euclidian topology), we will denote by int(A) (the interior of A) the greatest open subset of A(int(A) = ∪{G:Gopen and G⊆A}). 4A two dimensional linear function fis a function of the following type f(x, y) = ax +by 2.1 Dynamical Systems Definition 1. Adynamical transition system is a triple S= (X, T, Σ), where Xis a set (the set of points of the system), T:X→X(the transition function that produces the evolution of the system), and Σis a collection of subsets of X (this component is only considered in the case we are interested in the symbolic behavior of the system). Remark 1. Usually, we will require Σto be a partition of X, or at least to be a collection of pairwise disjoint subsets of X(in the case we are interested in the dynamical behavior of some parts of X, using the rest as auxiliary computation). Also, we will see Σas an alphabet, and we will study the language generated by the system on this alphabet. Definition 2. Let S= (X, T, Σ)a dynamical system, and x∈X. The sequence {xn}n≥0, such that: –x0=x, –for every n≥0,xn+1 =T(xn). is called the orbit of xby the system S, and it will be denoted as OS(x). x0 x1 x2x6 x5 x7 x4 I1 I2 I3I4 X Fig. 1. Example of a dynamical system with an orbit in it In Figure 1 we have a dynamical system S= (X, T, Σ) = {I1, I2, I3, I4}), where a partial orbit of a point, x0, is shown. Definition 3. Let S= (X, T, Σ)be a dynamical system, and x∈X. Let’s associate the set X\∪w∈Σwto the element ε(the empty word). The symbolic dynamics of xin terms of Σis the set: SS(x) = {w∈Σ∗:∀n≥0 (OS(x)n∈wn)} Where we use the notation w=w1w2. . .. In example above, SS(x0) = I1I2I2I1εI4I2=I1I2I2I1I4I2. Note that point x5in the orbit has no representation in its symbolic dynamics. Remark 2. If Σis a collection of pairwise disjoint subsets of X, then for every point x∈X,SS(x) has only one element. Definition 4. Let S1= (X1, T1, Σ1)and S2= (X2, T2, Σ2)two dynamical systems. We will say that S2simulates S1if there exists an injection ϕ:X1,→X2, and an injection σ:Σ1,→Σ2such that for every x∈X1, we have: SS2(ϕ(x)) = bσ(SS1(x)) where bσ:Σ∗ 1,→Σ∗ 2is the morphism generated by σ. 2.2 Pseudo Billiard Systems Let us introduce the pseudo billiard model that already appeared in a different context and became an abstract framework for some practical problems. In this system we consider a number of segments with vector fields assigned to them. The computation in this system can be described by the dynamics of the particle, which initially moves with the constant velocity (in a particular direction) inside a given region (not necessarily a polyhedron) and changes it instantaneously at the moment of a collision with the boundary to the velocity defined by a given vector field on the boundary. We start with a more general definition for PBS’s, where we have no constraints on distributing the segments around the space. In this case, a particle can touch the segments by both faces, and therefore it may cross them by the action of their projection vectors. Definition 5. A Pseudo Billiard System (PBS) is a pair (A,V), where Ais a set of pairwise disjoint segments in R2(closed, open or semi-open), and V= {vA}A∈A is a set of vectors in R2−{(0,0)}(vAis called the projection vector of A). The dynamics of a particle in PBS can be defined as follows. Let a particle P that is represented by a vector xand is located on a segment A∈ A, i.e. x∈A. The transition function that moves P from xto a position x0can be defined as follows: x0=x+λvA, where λ= min{δ > 0 : x+δvA∈SA0∈A A0}. We will suppose that for every x∈Athere exists such a λ(the particle is trapped inside the system). a) x0 x1 x2 x3 b) x0 x1 x2 x3 Fig. 2. An example of partial orbit: a) in a PBS, b) in a reflecting PBS The PBS can be seen as a dynamical transition system S= (X, T, Σ) where: –X=SA∈A A, –T(x) = x+λvA, where x∈Aand λ= min{δ > 0 : x+δvA∈SA0∈A A0} –Σis any collection of subsets of X(usually it will be a subset of A). Definition 6. A PBS is reflecting, if for every A∈ A, the set T−1(A)and T(A)are in the same half-plane determined by A. 2.3 Piecewise Affine Maps Definition 7. We say that f:R→Ris a piecewise affine map (PAM) if there exists a partition of dom(f)in a finite number of intervals of R(we allow the intervals to be closed, open or semi-open intervals), I, and for every I∈ I,there exists aI, bI∈Rsuch that: ∀x∈I, f(x) = aIx+bI. Remark 3. If we have f(dom(f)) ⊆dom(f), then we can consider a dynamical system associated to it, S= (X, T, Σ) where: –X=dom(f), –T=f(x) and –Σis any collection of subsets of X(usually it will be a subset of I). I1I2 I3I4I5 x1 x2 x0 x3 Fig. 3. An example of partial orbit in a PAM (represented on the diagonal) Definition 8. A rational function is a function defined as a ratio of polynomials. For a single variable xa typical rational function is therefore f(x) = P(x)/Q(x), where Pand Qare polynomials in xas indeterminate, and Qis not the zero polynomial. We also give the definition of a more general class of rational functions that we are going to study in the paper. We define it over Qto show that even in this case the predictability of its behaviour is an undecidable problem. Definition 9. A Piecewise (one-dimensional) rational map (PRM) is a function that is defined on a finite sequence of disjoint intervals I−= (−∞, r−],I+= [l+,+∞),Ii= [li, ri]with r−, l+, li,ri∈Q,i= 1..k and uses rational functions for different parts of its domain. The computation in the above system can be understood as a generation of sequence of points. One of the obvious problems that arises in such systems is a point-to-point reachability problem that can be formulated as follows: Problem 1. Given two points x, y ∈Qand a one-dimensional piecewise map P. Decide whether yis reachable from xin P. 3 Equivalence between Dynamical Systems In this section we will study the equivalence between the models introduces above. We will say that two models are equivalent if for every system of one type there exists a system of another type that simulates it and vice versa. In particular we are giving geometrical constructions to show the equivalence of onedimensional PAM, planar PBS and planar reflective PBS. Moreover using the result that model of hierarchical piecewise constant derivative systems (HPCDs) is equivalent to one-dimensional PAMs we can state that planar PBS is equivalent to two-dimensional HPCDs (see [2]). Hence the complexity that can be obtained with any of them is the same. 3.1 PAM simulates PBS The first step through the equivalence will be devoted to prove that any PBS system (reflecting or not) can be simulated by a PAM system. Theorem 1. For every Pseudo Billiard System, {A,V}, there exists a Piecewise Affine Map that simulates it. Proof. Let us consider a PBS given by a set of segments A={Ai}and a set of associated projection vectors {vi}. You can see an example on Figure 4 .a. a) { } A1 A2 A3 A4 ~v1 ~v2 ~v3 ~v4 b) A1 1,2 A1 1,4 A1 1,3A2 1,4 A1 A2 A3 A4 ~v1 Fig. 4. a) Example of PBS to be simulated by a PAM; b) Projection of A1on other segments of the PBS, and the partition on A1that it generates The dynamics of the PBS is defined by projecting every point of Aion some other segment by using the projection vector vi. It is clear, from the definition of PBS, that we can make a partition of Aiin segments, {Ak i,j}, in such a way that every point of {Ak i,j}is projected on a point of Aj(see Figure 4 .b). The next step is to associate for every segment of the system, Ai, an interval on the line, Ii, by using an affine bijection, µi:Ai→Ii. Also, we will require these intervals to be pairwise disjoint. For every i, j, k such that Ak i,j 6=∅, the projection Pk i,j :Ak i,j →Ajis an affine transformation. Also, all the functions µi are affine transformations. a) b) c) d) Fig. 5. Projections: a) from A1; b) from A2; c) from A3; d) from A4 Hence, we can define an affine map fi,j,k :µi(Ak i,j)→µj(Aj) x7→ µj(Pk i,j(µ−1 i(x))) Since {Ak i,j}i,j,k is a partition of the points of the PBS, {Ik i,j}i,j,k is a partition of the set of intervals considered, hence we obtain that the map f:[ i,j,k Ik i,j →[ i,j,k Ik i,j x7→ fi,j,k(x),if x∈Ik i,j is a piecewise affine map. A1A2A3A4 A1 A2 A3 A4 Fig. 6. PAM obtained after the process In order to prove the dynamical simulation, let us consider the following injection between the set of points of the systems: ϕ:SAi,→SIi x7→ µi(x),if x∈Ai. If Σis the subset of Athat produces the symbolic dynamics, then Σ0= {ϕ(I) : I∈Σ}is the collection to be considered in the PAM, and σ:Σ→Σ0 defined by σ(I) = ϕ(I) is the injection for the dynamics. From the construction, it is obvious that fsimulates the given PBS. Lemma 1. The number of affine functions we need in order to simulate a PBS is bounded5by |A|(|A|+ 2). Proof. Idea: for every segment of the PBS, the partition we need to make all possible projections on the other segments is bounded in size by |A|+ 2. 3.2 PBS simulates PAM Next, we will prove that for any PAM we can build a PBS simulating its dynamical behavior. Indeed, we will see that they can be simulated using only reflecting PBS’s, hence there is no difference (regarding the dynamical complexity of the system) in using a general PBS or restrict ourselves to reflecting PBS’s. Nevertheless, we will prove in a first step that, for every PAM we can get a general PBS (usually not reflecting) that simulates the given PAM. The proof is based on the graphical idea about how to compute the orbit of a point directly on the graph generated by the PAM (where we consider the dynamics on the diagonal rather than on the Xaxis) using the iterated projections between the affine map and the diagonal. Fig. 7. PBS associated to a PAM In this example we can see that the PBS obtained by the dynamics of the PAM over the diagonal is, in general, a non reflecting one, because depending its definition, we will need to cross some of the affine map graphs to reach the diagonal. In any case, it is not a problem, because if we must cross one map from another one, it is because both of them are in the same half-plane from the diagonal, and then their associated vectors are parallel and in the same direction. It is easy to see that, if we restrict the dynamics on the set of segments over the diagonal, rather than on the Xaxis, the system we obtain is equivalent to the original one. 5In case of reflecting PBSs, the bound can be reduced to |A| + 2 Theorem 2. For every Piecewise Affine Map there exists a Pseudo Billiard System that simulates it. Proof. Let f=Sn i=1 fia PAM where every fiis an affine map over an interval Ii. We consider the following segments on R2: –For every Ii= [ai, bi], we consider its projection on the diagonal, x=y, that we note as Ai. –For every Iiwe consider the segment given by (ai, fi(ai)) −(bi, fi(bi)), that we note as f(Ai). We can consider that there is no intersection between the interior of segments of the PAM (otherwise if any Aiintersects with some f(Aj), we consider the intersection point, and subdivide both segments, leaving this point in the diagonal segment (in Figure 7 we have split the second affine function in order to have segments with no intersection in their interiors). Of course, the obtained PAM is equivalent to the original one. The vectors associated with every segment is given by the following rule: for every i –if int(f(Ai)) is inside the half-plane x<y(the upper half) then the vector associated to Aiis (0,1), and the vector associated to f(Ai) is (1,0). –if int(f(Ai)) is inside the half-plane x > y (the lower half) then the vector associated to Aiis (0,−1), and the vector associated to f(Ai) is (−1,0). In order to prove the dynamical simulation, let us consider the following injection between the set of points of the systems: ϕ:SIi,→SAi x7→ (x, x) and, following the same procedure as in theorem 1, the same injection between the dynamics of the systems. From the construction, it is obvious that the resulting PBS simulates the given PAM (note that we use only a part of the dynamics of the PBS, considering only the dynamics on the diagonal, and not the evolution of the points through the other segments, necessary for the correct computing of the evolution, but not for the dynamics itself). 3.3 Reflecting PBS simulates PAM Theorem 3. For every Piecewise Affine Map there exists a Reflecting Pseudo Billiard System that simulates it. Proof. Let f:I→Ibe a PAM expressed in such a way that I=Sn i=1 Iiis union of pairwise disjoint intervals, and for every i,f|Ii=fi, where fi(x) = aix+biis an affine function. The first step of the proof consists in assigning to every interval of the PAM a segment in R2where we simulate the dynamics of the system. Since fi:Ii→I