corps fini

[chaos1.git] / main.tex

diff --git a/main.tex b/main.tex
index 8e7f34b71c25b04a1da42419c9bd664974f2c412..cee88400c5a74d8f73babf97e75ca1fb7f6a49aa 100644 (file)
--- 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}
 
 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}
 
 
 \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
 
 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.
 
 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).
   \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$.
   {\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.
 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.
 
 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$
 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*}
 %\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
 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)$.
 
 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 
 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.
 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 
 $$
 
 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$.
 
 
 %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
 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
 
 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}$]
 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.
 
 
 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(
 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
  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
 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.
 
 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.
 
 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}
 
 \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}
 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
 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}
 \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 .$$
 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.
 
 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}
 \bibliography{chaos-paper}% Produces the bibliography via BibTeX.
 
 \end{document}