The Non-Archimedean Theory of Discrete Systemsстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 4 февраля 2014 г.
Аннотация:In the paper, we study behaviour of discrete dynamical systems (automata)
w.r.t. transitivity;
that is, speaking loosely, we consider
how diverse may be behaviour of the system w.r.t. variety
of word transformations
performed by the system: We call a system completely transitive if, given
arbitrary pair $a,b$ of finite words that have equal lengths, the system $\mathfrak A$, while evolution during (discrete) time,
at a certain moment transforms $a$ into $b$.
To every system $\mathfrak A$, we put into a correspondence a family $\Cal
F_{\mathfrak
A}$ of continuous mappings of a suitable non-Archimedean metric space and show that the
system is completely transitive if and only if the family $\Cal
F_{\mathfrak
A}$ is ergodic w.r.t. the Haar measure; then we find easy-to-verify
conditions the
system must satisfy to be completely transitive. The theory can be applied
to analyse behaviour of straight-line computer programs (in particular,
pseudo-random
number generators that are used in cryptography and simulations) since basic CPU instructions (both numerical and logical) can be considered as continuous mappings of a (non-Archimedean)
metric space $\Z_2$ of 2-adic integers.