Reachability problem for continuous piecewise-affine mappings of a~circle having degree~2

O. M. Kurganskyy

Prikladnaya Diskretnaya Matematika. Supplement, no. 7 (2014), pp. 26-28

Résumé

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.

Détail

Keywords: deterministic chaos, cryptography, piecewise-affine mapping, reachability problem.