From: Jean-François Couchot Date: Tue, 20 Sep 2011 14:42:22 +0000 (+0200) Subject: corps fini X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/chaos1.git/commitdiff_plain/999fadfcb0b5ed18bd495364a07850278fade07d?hp=-c corps fini --- 999fadfcb0b5ed18bd495364a07850278fade07d diff --git a/main.tex b/main.tex index 8e7f34b..cee8840 100644 --- a/main.tex +++ b/main.tex @@ -204,9 +204,9 @@ section. In what follows and for any function $f$, $f^n$ means the composition $f \circ f \circ \hdots \circ f$ ($n$ times) and an \emph{iteration} -of a \emph{dynamical system} the step that consists in -updating the global state $x$ with respect to a function $f$ s.t. -$x^{t+1} = f(x^t)$. +of a \emph{dynamical system} is the step that consists in +updating the global state $x^t$ at time $t$ with respect to a function $f$ +s.t. $x^{t+1} = f(x^t)$. \subsection{Devaney's chaotic dynamical systems} @@ -242,57 +242,39 @@ point dependence on initial conditions. Topological transitivity is checked when, for any point, any neighborhood of its future evolution eventually overlap with any other -given region. More precisely, - -\begin{definition} \label{def2} -A continuous function $f$ on a topological space $(\mathcal{X},\tau)$ -is defined to be {\emph{topologically transitive}} if for any pair of -open sets $U$, $V \in \mathcal{X}$ there exists -$k \in -\mathds{N}^{\ast}$ - such that -$f^k(U) \cap V \neq \emptyset$. -\end{definition} - -This property implies that a dynamical system cannot be broken into -simpler subsystems. +given region. This property implies that a dynamical system +cannot be broken into simpler subsystems. Intuitively, its complexity does not allow any simplification. On the contrary, a dense set of periodic points is an element of regularity that a chaotic dynamical system has to exhibit. -\begin{definition} \label{def3} -A point $x$ is called a {\emph{periodic point}} for $f$ of period~$n \in -\mathds{N}^{\ast}$ if $f^{n}(x)=x$. -\end{definition} - -\begin{definition} \label{def4} -$f$ is said to be {\emph{ regular}} on $(\mathcal{X},\tau)$ if the set of - periodic points for $f$ is dense in $\mathcal{X}$ ( for any $x \in +However, chaos need some regularity to ``counteracts'' +the effects of transitivity. +%\begin{definition} \label{def3} +We recall that a point $x$ is {\emph{periodic point}} for $f$ of +period~$n \in \mathds{N}^{\ast}$ if $f^{n}(x)=x$. +%\end{definition} +Then, the map +%\begin{definition} \label{def4} +$f$ is {\emph{ regular}} on $(\mathcal{X},\tau)$ if the set of + periodic points for $f$ is dense in $\mathcal{X}$ (for any $x \in \mathcal{X}$, we can find at least one periodic point in any of its neighborhood). -\end{definition} - -This regularity ``counteracts'' the effects of transitivity. Thus, -due to these two properties, two points close to each other can behave -in a completely different manner, leading to unpredictability for the -whole system. Then, - -\begin{definition} \label{sensitivity} -$f$ has {\emph{ sensitive dependence on initial conditions}} if there - exists $\delta >0$ such that, for any $x\in \mathcal{X}$ and any - neighborhood $V$ of $x$, there exist $y\in V$ and $n > 0$ such that - $d\left(f^{n}(x), f^{n}(y)\right) >\delta $. The value $\delta$ is called the +%\end{definition} + Thus, + due to these two properties, two points close to each other can behave + in a completely different manner, leading to unpredictability for the + whole system. + +Let we recall that $f$ +has {\emph{ sensitive dependence on initial conditions}} if there +exists $\delta >0$ such that, for any $x\in \mathcal{X}$ and any +neighborhood $V$ of $x$, there exist $y\in V$ and $n > 0$ such that +$d\left(f^{n}(x), f^{n}(y)\right) >\delta $. The value $\delta$ is called the {\emph{constant of sensitivity}} of $f$. -\end{definition} - -Finally, -\begin{definition} \label{def5} -The dynamical system that iterates $f$ is {\emph{ chaotic according to Devaney}} -on $(\mathcal{X},\tau)$ if $f$ is regular, topologically transitive, +Finally, The dynamical system that iterates $f$ is {\emph{ chaotic according to Devaney}} on $(\mathcal{X},\tau)$ if $f$ is regular, topologically transitive, and has sensitive dependence to its initial conditions. -\end{definition} - In what follows, iterations are said to be \emph{chaotic according Devaney} when corresponding dynamical system is chaotic according Devaney. @@ -317,8 +299,8 @@ of integers: $\{a, a+1, \hdots, b\}$, where $a~<~b$. In that section, a system under consideration iteratively modifies a collection of $n$~components. Each component $i \in \llbracket 1; n \rrbracket$ -takes its value $x_i$ among the domain $\Bool=\{0,1\}$. A~{\it - configuration} of the system at discrete time $t$ is the vector +takes its value $x_i$ among the domain $\Bool=\{0,1\}$. +A \emph{configuration} of the system at discrete time $t$ is the vector %\begin{equation*} $x^{t}=(x_1^{t},\ldots,x_{n}^{t}) \in \Bool^n$. %\end{equation*} @@ -335,23 +317,26 @@ $N(i,x)=(x_1,\ldots,\overline{x_i},\ldots,x_n)$ is the configuration obtained by switching the $i-$th component of $x$ ($\overline{x_i}$ is indeed the negation of $x_i$). Intuitively, $x$ and $N(i,x)$ are neighbors. The discrete iterations of $f$ are represented by the -oriented {\it graph of iterations} $\Gamma(f)$. In such a graph, +oriented \emph{graph of iterations} $\Gamma(f)$. In such a graph, vertices are configurations of $\Bool^n$ and there is an arc labeled $i$ from $x$ to $N(i,x)$ if and only if $f_i(x)$ is $N(i,x)$. -In the sequel, the {\it strategy} $S=(S^{t})^{t \in \Nats}$ is the +In the sequel, the \emph{strategy} $S=(S^{t})^{t \in \Nats}$ is the sequence defining which component to update at time $t$ and $S^{t}$ denotes its $t-$th term. This iteration scheme that only modifies one element at each iteration -is clasically refered as \emph{asynchronous iterations}. -More préciselly, we have here +is classically referred as \emph{asynchronous iterations}. +More precisely, we have here for any $i$, $1\le i \le n$, $$ +\left\{ \begin{array}{l} +x^{0} \in \Bool^n \\ x^{t+1}_i = \left\{ \begin{array}{l} f_i(x^t) \textrm{ if $S^t = i$} \\ x_i^t \textrm{ otherwise} \end{array} \right. +\end{array} \right. $$ Next section shows the link between asynchronous iterations and @@ -414,7 +399,7 @@ classical iterations of a dynamical system. %element. But it can be extended by considering subsets for $S^t$. -To study topological properties of these iteations, we are then left to +To study topological properties of these iterations, we are then left to introduce a {\emph{ distance}} $d$ between two points $(S,x)$ and $(\check{S},\check{x})\in \mathcal{X} = \llbracket1;n\rrbracket^\Nats. \times \Bool^{n}$. It is defined by @@ -443,7 +428,7 @@ measures the difference between the strategies. The relation between $\Gamma(f)$ and $G_f$ is clear: there exists a path from $x$ to $x'$ in $\Gamma(f)$ if and only if there exists a -strategy $s$ such that the parallel iteration of $G_f$ from the +strategy $s$ such that iterations of $G_f$ from the initial point $(s,x)$ reaches the configuration $x'$. Using this link, Guyeux~\cite{GuyeuxThese10} has proven that, \begin{theorem}%[Characterization of $\mathcal{C}$] @@ -460,8 +445,8 @@ In that case, iterations of the function $G_f$ as defined in Eq.~(\ref{eq:Gf}) are chaotic according to Devaney. -Let us then consider two function $f_0$ and $f_1$ both in -$\Bool^n\to\Bool^n$ defined as follows that are used all along this article. +Let us then define two function $f_0$ and $f_1$ both in +$\Bool^n\to\Bool^n$ that are used all along this article. The former is the vectorial negation, \textit{i.e.}, $f_{0}(x_{1},\dots,x_{n}) =(\overline{x_{1}},\dots,\overline{x_{n}})$. The latter is $f_1\left(x_1,\dots,x_n\right)=\left( @@ -520,12 +505,13 @@ given as outside input, then the sequence of successive published output vectors $\left(x^t\right)^{t \in \mathds{N}^{\ast}}$ is exactly the one produced by the chaotic iterations formally described in -Eq.~(\ref{eq:CIs}). It means that mathematically if we use similar +Eq.~(\ref{eq:Gf}). It means that mathematically if we use similar input vectors they both generate the same successive outputs $\left(x^t\right)^{t \in \mathds{N}^{\ast}}$, and therefore that they are equivalent reformulations of the iterations of $G_{f_0}$ in $\mathcal{X}$. Finally, since the proposed neural network is built to -model the behavior of $G_{f_0}$, which is chaotic according to +model the behavior of $G_{f_0}$, whose iterations are + chaotic according to Devaney's definition of chaos, we can conclude that the network is also chaotic in this sense. @@ -610,6 +596,10 @@ like topology to establish, for example, their convergence or, contrarily, their unpredictable behavior. An example of such a study is given in the next section. +\JFC{Ce qui suit est davantage qu'un exemple.Il faudrait +motiver davantage, non?} + + \section{Topological properties of chaotic neural networks} \label{S4} @@ -676,7 +666,8 @@ intrinsically complicated and it cannot be decomposed or simplified. Furthermore, those recurrent neural networks exhibit the instability property: \begin{definition} -A dynamical system $\left( \mathcal{X}, f\right)$ is unstable if for +A dynamical system $\left( \mathcal{X}, f\right)$ is \emph{unstable} +if for all $x \in \mathcal{X}$, the orbit $\gamma_x:n \in \mathds{N} \longmapsto f^n(x)$ is unstable, that means: $\exists \varepsilon > 0$, $\forall \delta>0$, $\exists y \in \mathcal{X}$, $\exists n \in @@ -707,7 +698,7 @@ at least $\varepsilon$ apart in the metric $d_n$. Denote by $H(n, \varepsilon)$ the maximum cardinality of an $(n, \varepsilon)$-separated set, \begin{definition} -The {\it topological entropy} of the map $f$ is defined by (see e.g., +The \emph{topological entropy} of the map $f$ is defined by (see e.g., Ref.~\cite{Adler65} or Ref.~\cite{Bowen}) $$h(f)=\lim_{\varepsilon\to 0} \left(\limsup_{n\to \infty} \frac{1}{n}\log H(n,\varepsilon)\right) \enspace .$$ @@ -1140,6 +1131,21 @@ consequences in biology, physics, and computer science security fields will be stated. Lastly, thresholds separating systems depending on the ability to learn their dynamics will be established. +% \appendix{} + + + +% \begin{definition} \label{def2} +% A continuous function $f$ on a topological space $(\mathcal{X},\tau)$ +% is defined to be {\emph{topologically transitive}} if for any pair of +% open sets $U$, $V \in \mathcal{X}$ there exists +% $k \in +% \mathds{N}^{\ast}$ +% such that +% $f^k(U) \cap V \neq \emptyset$. +% \end{definition} + + \bibliography{chaos-paper}% Produces the bibliography via BibTeX. \end{document}