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.
O. M. Kurganskyy. Reachability problem for continuous piecewise-affine mappings of a circle having degree 2. Prikladnaya Diskretnaya Matematika. Supplement, no. 7 (2014), pp. 26-28. http://geodesic.mathdoc.fr/item/PDMA_2014_7_a9/
@article{PDMA_2014_7_a9,
author = {O. M. Kurganskyy},
title = {Reachability problem for continuous piecewise-affine mappings of a~circle having degree~2},
journal = {Prikladnaya Diskretnaya Matematika. Supplement},
pages = {26--28},
year = {2014},
number = {7},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/PDMA_2014_7_a9/}
}
TY - JOUR
AU - O. M. Kurganskyy
TI - Reachability problem for continuous piecewise-affine mappings of a circle having degree 2
JO - Prikladnaya Diskretnaya Matematika. Supplement
PY - 2014
SP - 26
EP - 28
IS - 7
UR - http://geodesic.mathdoc.fr/item/PDMA_2014_7_a9/
LA - ru
ID - PDMA_2014_7_a9
ER -
%0 Journal Article
%A O. M. Kurganskyy
%T Reachability problem for continuous piecewise-affine mappings of a circle having degree 2
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2014
%P 26-28
%N 7
%U http://geodesic.mathdoc.fr/item/PDMA_2014_7_a9/
%G ru
%F PDMA_2014_7_a9
[1] Ptitsyn N. V., Prilozhenie teorii determinirovannogo khaosa v kriptografii, Izd-vo MGTU im. N. E. Baumana, M., 2002, 80 pp.
[2] Savchenko A. Ya., Kovalev A. M., Kozlovskii V. A., Scherbak V. F., “Inverse dynamical systems in secure communication and its discrete analogs for information transfer”, Proc. NDES, 2003, 112–116
[3] Delvenne J.-C., “What is a universal computing machine?”, Appl. Math. Comput., 215:4 (2009), 1368–1374 | DOI | MR | Zbl
[4] Kurganskyy O., Potapov I., Sancho-Caparrini F., “Reachability problems in low-dimensional iterative maps”, Int. J. Found. Comput. Sci., 19:4 (2008), 935–951 | DOI | MR | Zbl
[5] Asarin E., Mysore V., Pnueli A., Schneider G., “Low dimensional hybrid systems – decidable, undecidable, don't know”, Inform. Comput., 211 (2012), 138–159 | DOI | MR | Zbl
