Abstract:
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_2\colon\mathbb{R/Z\to R/Z}$ where $E_2(x)=2x\pmod1$. It is known that the orbit $O(x)$ of $E_2$ is uniformly distributed for almost all $x\in\mathbb{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 $E_2$ lies in the complexity of its initial state. Thus the mathematical fact that $E_2$ 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_2$ shows chaotic behaviour not only for real but also for some rational states. It makes them interesting in problems of cryptographic information transformation.