Computation in One-Dimensional Piecewise Maps

Computation in One-Dimensional Piecewise Maps Oleksiy Kurganskyy1, Igor Potapov2, and Fernando Sancho Caparrini3 1Institute of Applied Mathematics and Mechanics, NAS of Ukraine 2Computer Science Department, University of Liverpool 3Department of Computer Science and AI, University of Seville Abstract. In this paper we show that the one-dimensional Piecewise Affine Maps (PAMs) are equivalent to planar Pseudo-Billiard Systems (PBSs) or so called “strange billiards”. The reachability problem for PAMs is still open, however the more general model of rational onedimensional maps is shown to be universal with undecidable reachability problem. 1 Introduction In the present work we investigate a class of hybrid systems defined by onedimensional piecewise maps. We mainly interested in a class of one-dimensional piecewise-affine maps (PAMS) for which reachability problem is still open. It was recently shown that PAM is equivalent to hierarchical piecewise constant derivatives system (HPCD)[1]. In this paper we show that PAM is equivalent to planar pseudo-billiard system (PBS). PBS is also referred as “strange billiards” model that is a well known object in bifurcation and chaos theory [3]. HPCD is a hybrid automaton where each state is defined by planar piecewise constant derivatives system (PCD). In contrast to HPCD, the model of PBS can also be seen as two dimensional linear hybrid automaton but with only one state. In the second part of this paper we are exploring the complexity of more general class of one-dimensional maps that includes a class of affine maps. We show that the one-dimensional piecewise rational map (PRM) is universal model of computation with undecidable reachability problem. Moreover it is possible to show that there is a particular map, that corresponds to the universal Minsky machine, for which the reachability problem is undecidable. 2 Equivalence Between PBS and PAM The pseudo billiard model is already appeared in a different context and became an abstract framework for several practical problems. By the pseudo billiard we understand a number of segments with assigned to them vector fields. 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 (not necessarily a constant one) 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 1. A Pseudo Billiard System (PBS) is a pair (A,V),whereAis 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(vAis called the projection vector of A). The dynamic 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 move P from xto a position xcan be defined as follows: x=x+λvA,wherex∈Aand λ=min{δ>0:x+δvA∈A∈A A}. In this case we say that xis (directly) reachable from xand we denote it as x⇒x. Since we have a set of pairwise disjoint segments it is clear that for any xthere is a unique xif x⇒xand x=x. We also assume that minimum in λ always exists (particles do not go to infinity). Definition 2. APBSisreflecting, if for every A∈A, two sets of points Pre(A) and Post(A)are in the same half-plane determined by A,wherePre(A)is a set of points from which points on Aare directly reachable and Post(A)is a set of points which are directly reachable from points on A. Definition 3. We say that f:R→Ris piecewise affine map (PAM) if there exists a partition of dom(f)in a finite number of pairwise disjoint intervals of R(we allow the intervals to be closed, open or semi-open intervals), I,andfor every I∈I,there exists aI,b I∈Rsuch that: ∀x∈I, f(x)=aIx+bI. In this section we will study the equivalence between the models introduced 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, the equivalence of one-dimensional PAM, planar PBS and planar reflective PBS can be shown by several geometric constructions. Moreover using the result that model of hierarchical piecewise constant derivative systems (HPCDs) [1] is equivalent to one-dimensional PAMs we can state that planar PBS is equivalent to two-dimensional HPCDs. Hence the complexity that can be obtained with any of them is the same. Theorem 1. For every PBS, {A,V}, there exists a PAM that simulates it and the number of intervals in the PAM is bounded1by |A|(|A|+2). In the proof of Theorem 1 for every segment of the PBS, we construct all possible projections on the other segments that in their turn are bounded in size by |A|+2. 1In case of reflecting PBSs, the bound can be reduced to |A|+2. Theorem 2. Let fbe a PAM with Naffine functions. Let Rbe the number of affine maps, fi,withai<0. Then, there is a reflecting PBS simulating fusing, at most, 2N+Rreflecting segments. Proof. Let f:I→Ibe a PAM expressed in such a way that I=n i=1 Iiis union of pairwise disjoint intervals, and for every i,f|Ii=fi,wherefi(x)=aix+biis an affine function. The first step of the proof consists in assigning to every interval of the PAM asegmentinR2where we simulate the dynamic of the system. Since fi:Ii→I is affine, and Iiis an interval, fi(Ii) must be an interval too. Hence, the image of every interval of our partition must be inside an union of intervals of our partition that constitutes a larger interval. To make more direct the proof, we will maintain the continuity among intervals of fby considering for every interval, Ii⊆R,of f,thesegmentAi=Ii×{0}⊆R2. Now, we will simulate the dynamic of each affine map separately. Because the segments Aiare in the same line, we can’t go directly from one to another by using projections, therefore we will make use of auxiliary reflection segments to produce the same result as fproduces. Depending on the coefficients of the affine map, there are three different cases: Case 1: ai>0. In case 1 there is no flip from Aito fi(Ai), so we will need only one reflecting auxiliary segment to simulate the application of f,Bi. Case 2: ai<0. In case 2 there is a flip from Aito fi(Ai), so we will need two reflecting auxiliary segments, Biand B i, to simulate the function f. Case 3: ai=0.Incase3f(Ai) is a point, and we will make use of only one reflecting auxiliary segment, Bi, to project to this point. We can construct simultaneously all these segments with projection vectors on R2without disturbing one to each other, obtaining a reflecting PBS for a complete construction for PAM. It is easy to see from the above construction that the resulting PBS simulates the given PAM. From above construction, we can obtain an upper bound to the number of segments we need in a reflecting PBS to simulate a PAM. The presented method of construction is not efficient in general, but it works for any possible PAM. In a number of PAM’s, it is possible to reduce the number of elements of the PBS simulating the PAM. 3 Unpredictability in Rational Piecewise Maps Now we consider the more general class of rational functions. We define it over Q to show that even in this case the predictability of its behaviour is an undecidable problem. Definition 4. A Piecewise Rational Map (PRM) is a function that is defined on a finite sequence of disjoint intervals I−=(−∞,r −],I+=[l+,+∞),Ii=[li,r i] with r−,l +,l i,ri∈Q,i=1..k and uses rational functions 2for different parts of its domain I={I1∪...∪Ik}. 2f(x)=P(x)/Q(x) is a rational function, where Pand Qare polynomials in xas indeterminate, and Qis not the zero polynomial. Let Abe a 2-counter machine with a set of states S={1,2,...,n}. The configuration of Ais a triple [k,l,s]wherekand lare values of two counters and sis a current state of A. Let us define the mapping φ:N×N×N→Qthat is an isomorphism between a configuration [k,l,s]ofAand a rational number s+1 2k+13l+1 that is shifted to the interval (0,1): φ([k,l,s]) →1 10H(s+1 2k+13l+1 ),H =lg(|S|). Instead of classical Minsky machine with two counters c,dfrom now on we will consider the equivalent model of one counter machine where the counter holds an integer whose prime factorization is 2c·3d. Increment (decrement) of the counters cand dcan be done by multiplication (division) by 2 and 3 and zero testing corresponds to testing of divisibility by 2 and 3. Let Abe in a configuration [k,l,s]thatismappedtoxby φ. We can multiply/divide a virtual counter by 2 or/and 3 using the following expression (10Hx−s)2a3b+s 10H, where a,bare integers. For example, to check the emptiness of the first counter we need to add an integer 2k3l+1 using the expression 1 2(10Hx−s)+x.Thenwe can easily check whether a virtual counter is divisible by 2 iteratively applying x−2 until the point xin the interval [3,+∞). Finally a point xshould reach either the interval [2,3], which corresponds to k= 0, or the interval [1,2], which corresponds to k=0. In a similar way we can check divisibility by 3 from a state susing negative numbers. If x∈[s 10H,s+1 10H] we apply −(1 3(10Hx−s)+x)andthenx+3forany point in the interval (−∞,−4]. After that the number xshould appear in the interval [−4,−3], which corresponds to l=0orintheinterval[−3,−1], which corresponds to l=0. Theorem 3. One-dimensional piecewise rational map with a finite number of intervals is the universal model of computation. Thus, the problem whether a point x∈Qcan be mapped to y∈Qin a onedimensional piecewise rational map is undecidable. In contrast to the work [2] we have shown that the more natural extension of affine functions in dimension one is universal. As a next step it would be reasonable to raise a question about the complexity of piecewise linear rational maps. References 1. E. Asarin and G. Schneider. Widening the boundary between decidable and undecidable hybrid systems. CONCUR’2002,LNCS 2421 (2002) 193-208. 2. O.Kurganskyy, I.Potapov. Computation in One-Dimensional Piecewise Maps and Planar Pseudo-Billiard Systems. Unconventional Computation, LNCS 3699 (2005) 169-175. 3. K.Peters, U.Parlitz. Hybrid systems forming strange billiards. Int. J. of Bifurcations and Chaos, 19 (2003) 2575-2588.