The Non-Archimedean Theory of Discrete Systems

Abstract

In the paper, we study behavior of discrete dynamical systems (automata) w.r.t. transitivity; that is, speaking loosely, we consider how diverse may be behavior 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 ${\mathcal{F}}_{\mathfrak{A}}$ of continuous maps of a suitable non-Archimedean metric space and show that the system is completely transitive if and only if the family ${\mathcal{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 analyze behavior 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 maps of a (non-Archimedean) metric space ${\mathbb{Z}}_2$ of 2-adic integers.

The extended version of the talk given at MACIS-2011

References in corpus (1)

• Non-Archimedean Ergodic Theory and Pseudorandom Generators

Cited by in corpus (2)

• Secure cloud computations: Description of (fully)homomorphic ciphers within the P-adic model of encryption
• Quantization causes waves:Smooth finitely computable functions are affine