Reachability problem for continuous piece-wise-affine mappings of a circle having degree 2

For the continuous piecewise-affine mappings of a circle into itself having degree 2, the algorithmic decidability of the point-to-point reachability problem is proved. All these piecewise-affine mappings are topological conjugate to chaotic mapping E ₂ : R/Z ^ R/Z where E ₂(x) = = 2x (mod 1). It is known that the orbit O(x) of E ₂ is uniformly distributed for almost all x G R/Z, i.e. O(x) is chaotic. But none of the "almost all" x is representable in a computer because they all are infinite real numbers. The behaviour complexity of E2 lies in the complexity of its initial state. Thus the mathematical fact that E ₂ is chaotic is vacuous from the computer science point of view. But from the proof of the main result of this work, it follows that each continuous piecewise-affine mapping with rational coefficients that conjugate to E ₂ shows chaotic behaviour not only for real but also for some rational states. It makes them interesting in problems of cryptographic information transformation.

Keywords

Authors

References