

Soit ${\mathsf{N}}$ un entier naturel et $f$ une fonction de 
$\Bool^{{\mathsf{N}}}$ dans lui-même.


\subsection{Des itérations unaires aux itérations parallèles}

Dans le schéma unaire, à la  $t^{\textrm{ème}}$ itération, 
seul le  $s_{t}^{\textrm{ème}}$ 
composant (entre 1 et $n$) est mis à jour.
Pour une stratégie $s = \left(s_t\right)_{t \in \mathds{N}}$ 
(\textit{i.e.}, une séquence d'indices
de $\llbracket 1;\mathsf{N} \rrbracket$), on peut définir
la fonction $F_{f_u}: \Bool^{\mathsf{N}} \times \llbracket1;\mathsf{N}\rrbracket$
vers $\Bool^\mathsf{N}$ par 
\[
F_{f_u}(x,i)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_\mathsf{N}).
\]

Dans le schéma des itérations unaires pour une configuration initiale
$x^0\in\Bool^\mathsf{N}$ et une stratégie $s\in
\llbracket1;\mathsf{N}\rrbracket^\Nats$, les configurations $x^t$
sont définies par la récurrence
\begin{equation}\label{eq:asyn}
x^{t+1}=F_{f_u}(x^t,s_t).
\end{equation}


On peut alors construire l'espace 
$\mathcal{X}_u =
\Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}$ 
et la fonction d'itération $G_{f_u}$ définie  de 
$\mathcal{X}_u$ 
dans lui-même par 
\begin{equation}
G_{f_u}(x,s)=(F_{f_u}(x,s_0),\sigma(s)).
\label{eq:sch:unaire}
\end{equation}

Dans cette définition, la fonction 
$\sigma: \llbracket1;{\mathsf{N}}\rrbracket^{\Nats} \longrightarrow
 \llbracket1;{\mathsf{N}}\rrbracket^{\Nats} 
$
décale
la stratégie fournie en argument d'un élément vers la gauche en supprimant 
l'élément de tête. Ceci se formalise par 
$$
\sigma((u^k)_{k \in \Nats}) =  (u^{k+1})_{k \in \Nats}. 
$$


Ainsi, effectuer des itérations unaires sur la fonction 
$f$ selon une stratégie $s$ revient à effectuer des itérations
parallèles de la fonctions $G_{f_u}$ dans  $\mathcal{X}_u$.
La section suivante introduit une métrique sur $\mathcal{X}_u$.

\subsection{Une métrique pour $\mathcal{X}_u$}
Sur $\mathcal{X}_u$, 
on définit la distance $d$ entre les points $X=(x,s)$ et
$X'=(x',s')$ de $\mathcal{X}_u$ par 
\[
d(X,X')= d_H(x,x')+d_S(s,s'),~\textrm{où}~
\left\{
\begin{array}{l}
\displaystyle{d_H(x,x')=\sum_{i=1}^n |x_i-x'_i|}\\[5mm] 
\displaystyle{d_S(s,s')=\frac{9}{n}\sum_{t\in\Nats}\frac{|s_t-s'_t|}{10^{t+1}}}.
\end{array}
\right.\,.
\]
On note que dans le calcul de $d_H(x,x')$-- 
appelée distance de Hamming entre $x$ et $x'$-- 
les termes $x_i$ et $x'_i$ sont considérés comme des entiers naturels 
égaux à $0$ ou à $1$ et que le calcul est effectué dans $\Z$.
De plus, la partie entière 
$\lfloor d(X,X')\rfloor$ est égale à $d_H(x,x')$ soit la distance 
de Hamming entre $x$ et $x'$. 
On remarque que la partie décimale est inférieure à $10^{-l}$ si
et seulement si les $l$ premiers termes des deux stratégies sont égaux. 
De plus, si la 
$(l+1)^{\textrm{ème}}$ décimale  
de $d_S(s,s')$ 
n'est pas nulle, alors $s_l$ est différent de  $s'_l$. 

Se pose la question de caractériser les fonctions $f$ telles que 
les itérations de $G_{f_u}$ associées à leurs itérations unaires 
sont chaotiques dans $\mathcal{X}_u$. La section suivante 
apporte une réponse à cette question. 


\subsection{Caractérisation des fonctions rendant 
chaotiques $G_{f_u}$ sur $\mathcal{X}_u$}


On peut tout d'abord démontrer que pour toute fonction booléenne $f$, 
$G_{f_u}$ est continue sur $\mathcal{X}_u$ (cf annexe~\ref{anx:cont}).   

Pour caractériser les fonctions rendant chaotiques dans $\mathcal{X}_u$ les itérations de $G_{f_u}$ 
on se focalise donc que sur la régularité et sur la transitivité de $G_{f_u}$.
Ceci se réalise en établissant les relations d'inclusion entre 
les ensembles $\mathcal{T}$ des fonctions topologiquement transitives, 
$\mathcal{R}$ des fonctions régulières  
et $\mathcal{C}$ des fonctions chaotiques définis respectivement ci-dessous:
\begin{itemize}
\item   $\mathcal{T}   =    \left\{f   :   \mathds{B}^n   \to
\mathds{B}^n \big/ G_{f_u} \textrm{ est transitive} \right\}$,
\item   $\mathcal{R}   =    \left\{f   :   \mathds{B}^n   \to
\mathds{B}^n \big/ G_{f_u} \textrm{ est régulière} \right\}$,
\item   $\mathcal{C}   =    \left\{f   :   \mathds{B}^n   \to
\mathds{B}^n  \big/  G_{f_u}  \textrm{  est chaotique} \right\}$.
\end{itemize}


On énonce les théorèmes successifs suivants.
Leur preuve est donnée en annexe~\ref{anx:chaos:unaire}.

\begin{theorem} $G_{f_u}$  est transitive si et seulement si 
 $\textsc{giu}(f)$ est fortement connexe.
\end{theorem}

\begin{theorem}
\label{Prop: T est dans R:u} $\mathcal{T} \subset \mathcal{R}$.
\end{theorem}

On peut conclure  que $\mathcal{C} = \mathcal{R} \cap \mathcal{T}
= \mathcal{T}$. On a alors la  caractérisation suivante:

\begin{theorem}%[Characterization of $\mathcal{C}$]
\label{Th:CaracIC}  
Soit $f:\Bool^n\to\Bool^n$. La fonction $G_{f_u}$ est chaotique  
si et seulement si $\textsc{giu}(f)$ est fortement connexe.
\end{theorem}









