\section{\@startsection
	{section
{3
{0pt
{-3.5ex plus -1ex minus -.2ex
{2.3ex plus.2ex
{\centering\normalfont\Large\scshape}}

\renewcommand\subsection{\@startsection
	{subsection
{2
{0pt
{-3ex plus -1ex minus -.2ex
{1ex plus.2ex
{\normalfont\large\bfseries}}

\renewcommand\subsubsection{\@startsection
	{subsubsection
{3
{0pt
{-1.5ex plus -1ex minus -.2ex
{0.8ex plus .2ex
{\normalfont\bfseries}}

\renewcommand\paragraph{\@startsection
	{paragraph
{4
{0em
{-1.2ex plus -0.4ex minus -.2ex
{0ex
{\normalfont\bfseries}}

\makeatother

\newcommand\A{\mathcal A}
\newcommand\B{\mathcal B}
\newcommand\R{\mathbb R}
\newcommand\N{\mathbb N}
\newcommand\Z{\mathbb Z}
\newcommand\Q{\mathbb Q}
\newcommand\U{\mathbb U}
\newcommand\s\sigma
\newcommand\az{\A^\Z}
\newcommand\bz{\B^\Z}
\newcommand\dc{d_C}

\newcommand\tx{\text}

\newcommand{\mathbf{V}}{\mathbf{V}}
\newcommand{\mathbf{R}}{\mathbf{R}}

\newcommand\dm{d_\mathcal M}

\newcommand\mes{\mathcal M}

\newcommand\Ba{\mathfrak{B}}
\newcommand\Merg{\mathcal{M}_{\s-\textrm{erg}}}
\newcommand\Mpsimix{\mathcal{M}_{\s-\textrm{mix}}}
\newcommand\Mpsiexp{\mathcal{M}_{\s-\textrm{erg}}^{\psi-\textrm{exp}}}
\newcommand\Mergeff{\mathcal{M}_{\s-\textrm{erg}}^{\textrm{comp}}}
\newcommand\Mergreff{\mathcal{M}_{\s-\textrm{erg}}^{\textrm{r-comp}}}
\newcommand\Meff{\mathcal{M}_{\s}^{\textrm{comp}}}
\newcommand\Mreff{\mathcal{M}_{\s}^{\textrm{r-comp}}}
\newcommand\add{\mathcal{V}}
\newcommand\Ms{\mathcal{M}_{\s}}
\newcommand\Ball{\mathbf{B}}
\newcommand\supp{\textrm{supp}}
\newcommand\F{F_\ast}
\newcommand\Mergfull{\Merg^\textrm{full}}
\newcommand\Mmixfull{\Mpsimix^\textrm{full}}

\newcommand{\mathfrak{K}}{\mathfrak{K}}

\newcommand\meas[1]{\widehat{\delta_{#1}}}

\theoremstyle{definition}
\newtheorem{definition}{Definition}
\newtheorem{remark}{Remark}
\newtheorem{example}{Example}

\theoremstyle{plain}
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{fact}{Fact}
\newtheorem{open}{Open question}
\newtheorem{corollary}{Corollary}

\newcounter{claimcount}[theorem]
\newcommand{\THMfont}[1]{{\sl #1}}
\newcommand{\Claim}[1]{\refstepcounter{claimcount} \vspace{0.4em}\noindent {\sc Claim \theclaimcount: \ }\THMfont{ #1}}
\newcommand{\bclaimprf}[1][Proof.~]{\begin{list}{}{\setlength{\leftmargin}{0.5em} \setlength{\rightmargin}{2em}\setlength{\listparindent}{1em}}\item
{\em #1}}

\newcommand{\eclaimprf}{ \hfill $\Diamond$~{\scriptsize {\tt Claim~\theclaimcount}}\end{list}}

\usepackage{xcolor}
\usepackage{framed}

\newcommand{\hspace{-0.1cm}{\hspace{-0.1cm}
\vbox to 9pt{\hbox {
\begin{tikzpicture}[scale=0.38]
\draw [fill=black!20!white] (0,0) rectangle (1,1);
\draw (0.5,0.5) node {{\footnotesize W}};
\end{tikzpicture}
}}\hspace{-0.1cm}}
\newcommand{\hspace{-0.1cm}{\hspace{-0.1cm}
\vbox to 9pt{\hbox{
\begin{tikzpicture}[scale=0.38]
\draw (0,0) rectangle (1,1);
\draw (0.5,0.5) node {{\footnotesize I}};
\end{tikzpicture}
}}
\hspace{-0.1cm}}

\newcommand{\hspace{-0.1cm}{\hspace{-0.1cm}
\vbox to 9pt{\hbox{
\begin{tikzpicture}[scale=0.38]
\draw (0,0) rectangle (1,1);
\draw (0.5,0.5) node {{\footnotesize M}};
\end{tikzpicture}
}}
\hspace{-0.1cm}}
\newcommand{\hspace{-0.1cm}{\hspace{-0.1cm}
\vbox to 9pt{\hbox{
\begin{tikzpicture}[scale=0.38]
\draw (0,0) rectangle (1,1);
\draw (0.5,0.5) node {{\footnotesize C}};
\end{tikzpicture}
}}
\hspace{-0.1cm}}

\newcommand{\fire}{\vbox to 9pt{\hbox{
\begin{tikzpicture}[scale=0.4]
\draw [dashed, fill=gray!20] (0,0) rectangle (1,1);
\draw (0.5,0.5) node{$F$};
\end{tikzpicture}
}}}
\newcommand{\lfire}{\vbox to 9pt{\hbox{
\begin{tikzpicture}[scale=0.23]
\draw [dashed, fill=gray!20] (0,0) rectangle (1,1);
\draw (0.5,0.5) node{{\tiny $F$}};
\end{tikzpicture}
}}}
\newcommand{\order}{\vbox to 9pt{\hbox{
\begin{tikzpicture}[scale=0.4]
\draw [dashed, fill=black!50] (0,0) rectangle (1,1);
\draw (0.5,0.5) node{$O$};
\end{tikzpicture}
}}}

\newcommand{\white}{\vbox to 9pt{\hbox{
\begin{tikzpicture}[scale=0.4]
\draw [dashed,] (0,0) rectangle (1,1);
\draw (0.5,0.5) node{$ $};
\end{tikzpicture}
}}}
\newcommand{\lwhite}{\vbox to 9pt{\hbox{
\begin{tikzpicture}[scale=0.23]
\draw [dashed,] (0,0) rectangle (1,1);
\draw (0.5,0.5) node{$ $};
\end{tikzpicture}
}}}

\newcommand{\block}{\vbox to 9pt{\hbox{
\begin{tikzpicture}[scale=0.4]
\draw [dashed, fill=black!50] (0,0) rectangle (1,1);
\draw (0.5,0.5) node{$ $};
\end{tikzpicture}
}}}

\renewcommand\alph[1]{\A_\texttt{#1}}

\newcommand\define\textbf

\newcommand{\textrm{Card}}{\textrm{Card}}
\newcommand{\textrm{Freq}}{\textrm{Freq}}

\newcommand{\todo}[1]{\textcolor{red}{To do:} \textcolor{blue}{#1}}

\title[Characterization of sets of limit measures after iteration of a CA]{Characterization of sets of limit measures after iteration of a cellular automaton on an initial measure}

\author{Benjamin Hellouin de Menibus}
\address{LATP, Aix-Marseille Universit\'e, 39, rue F. Joliot Curie,13453 Marseille Cedex 13, France }
\email{benjamin.hellouin@gmail.com}

\author{Mathieu Sablik}
\address{LATP, Aix-Marseille Universit\'e, 39, rue F. Joliot Curie,13453 Marseille Cedex 13, France }
\email{sablik@latp.univ-mrs.fr}
\urladdr{http://www.latp.univ-mrs.fr/$\sim$sablik/}
\subjclass[2010]{37B10,37B15,03D10,03D80}
\keywords{Symbolic Dynamics, Cellular automata, SRB measures,Turing machines}

\date{}
\begin{document}

\maketitle

\begin{abstract}The asymptotic behavior of a cellular automaton iterated on a random configuration is well described by its limit probability measure(s). In this
paper, we characterize measures and sets of measures that can be reached as limit points after iterating a cellular automaton on a simple initial measure, in the same
spirit as SRB measures. In addition to classical topological constraints, we exhibit necessary computational obstructions. With an additional hypothesis of
connectivity, we show these computability conditions are sufficient by constructing a cellular automaton realising these sets, using auxiliary states in order
to perform computations. Adapting this construction, we obtain a similar characterization for the Ces\`aro mean convergence,
a Rice theorem on the sets of limit points, and we are able to perform computation on the set of measures, i.e. the cellular automaton converges
towards a set of limit points that depends on the initial measure. Last, under non-surjective hypotheses, it is possible to remove auxiliary states from the construction.
\end{abstract}

\section*{Introduction}
A cellular automaton is a complex system defined by a local rule which acts synchronously and uniformly on the configuration space $\az$, where $\A$ is a finite
alphabet. These simple models have a wide variety of different dynamical behaviors. We are interested in the typical asymptotic behavior starting from a
random configuration, as this is usually done in simulations; different approaches stemmed from such observations. It is well-described by taking the iterated image of the initial measure under the action of
the cellular automaton, and considering the limit points of this sequence in the weak$^\ast$ topology.

It is natural to ask which sets of measures can be obtained as limit points in this way.
Obviously, any measure can be reached by iterating the identity on itself. Therefore, a more interesting approach is to start from some simple measure such as the uniform Bernoulli measure. In some sense, this corresponds to SRB measures which are “physically” relevant invariant measures obtained when starting from the Lebesgue measure in continuous dynamical systems~\cite{Young-2002}.

Formally speaking, given a simple initial measure $\mu$, we want to characterize all reachable $\add(F,\mu)$, the sets of accumulation
points of $(\F^t\mu)_{t\in\N}$, the sequence of the images of $\mu$ under the iterated action of $F$, and $\add'(F,\mu)$, the sets of accumulation points of
$\left(\frac{1}{t+1}\sum_{i=0}^t\F^i\mu\right)_{t\in\N}$, the Ces\`aro mean of the previous sequence, for all possible cellular automata $F$.

Previous works focused on the $\mu$-limit set, which corresponds to the union of the support of the limit measures~\cite{Kurka-Maass-2000,Kurka-2005}.
Very complex $\mu$-limit sets can be constructed~\cite{Boyer-Poupet-Theyssier-2006,Boyer-Delacourt-Sablik-2010}, and our construction is partly inspired from these works.\\

Describing limit measures has been done for only few concrete nontrivial examples. There are essentially two types of convergence quite well understood:
\begin{itemize}
\item convergence towards a simple measure: for example, the cyclic cellular automaton on three states introduced in~\cite{Fisch-1990}, starting from a Bernoulli
measure, converges towards a linear combination of Dirac on uniform configurations~\cite{Hellouin-Sablik-2011};
\item randomisation phenomenon for linear cellular automata: the Ces\`aro mean sequence of the iteration of a linear cellular automaton on a initial measure converges to the uniform Bernoulli measure as soon as the initial measure is in a large class which contains Markov
measures~\cite{Ferrari-Maass-Martinez-Ney-2000,Maass-Martinez-1998,Pivato-Yassawi-2002}.
\end{itemize}

For any cellular automaton, starting from a Bernoulli measure or a Markov measure, we obtain after a finite number of steps a hidden Markov chain which is well
understood~\cite{Boyle-Petersen-2011}. If we consider a computable initial
measure $\mu$ (which means that there is an algorithm that approximates at a known rate the probability that a word $u\in\A^*$ appears), then it is easy to see
that $\F^t\mu$ is also computable. For example, a Bernoulli or Markov measure is computable iff its parameters are computable real numbers.

The limit measure(s) are not necessarily computable since the speed of convergence is not known. Nevertheless, we show in Section~\ref{section:ComputableObstruction} that there exists necessary computational obstructions. The main problem is to prove the reciprocal, in other words: given a set of measures satisfying
the computational obstructions, construct a cellular automaton which, starting on any simple initial measure, reaches exactly this set asymptotically.
Similar computational obstructions appear when characterizing possible topological dynamics properties of subshifts of finite type or cellular automata:
possible entropies~\cite{Hochman-Meyerovitch-2010}, possible growth-type invariants~\cite{Meyerovitch-2011}, possible sub-actions~\cite{Hochman-2009,Aubrun-Sablik-2010}...
However, the construction is quite different here since starting from a random configuration requires to self-organize
the space, in the same spirit as the probabilistic cellular automaton of~\cite{Gacs-2001} which corrects the random perturbations.

In Section~\ref{section:Construction}, we construct a cellular automaton $F$ such that, starting from any shift-mixing probability measure $\mu$ with full support, the
limit points of the sequence of measures $(\F^t\mu)_{t\in\N}$ are described as the accumulation points of a computable polygonal path of measures supported by periodic orbits.
First of all the cellular automaton divides the initial configuration in segments and formats each segment using a method  similar to the one developed in~\cite{Delacourt-Poupet-Sablik-Theyssier-2011}. Computation takes place in a negligible part of each segment and the result is copied periodically on the rest of the segment. In order to have an arbitrarily large area of computation, segments are merged progressively in a controlled manner.
The difficulty of the construction is to synchronize all the operations to ensure the convergence.

In Section~\ref{section:RelatedProblem} we use the construction of Section~\ref{section:Construction} to solve some related problems, along with some open questions.
The results are, for a fixed measure $\mu$ in a large class of measures:
\begin{itemize}
 \item characterization of shift-invariant measures $\nu$ such that there exists a cellular automaton $F$ which verifies $\F^t\mu\underset{t\to\infty}{\longrightarrow}\nu$
(Corollary~\ref{cor:ConvUniqueMeasure});
 \item characterization of connected subsets of shift-invariant measures $\add$ such that there exists a cellular automaton $F$ which verifies $\add(F,\mu)=\add$ (Corollary~\ref{cor:ConvSetMeasure});
 \item characterization of subsets of shift-invariant measures $\add'$ such that there exists a cellular automaton $F$ which verifies $\add'(F,\mu)=\add'$ (Corollary~\ref{cor:ConvCesàroMeasure});
 \item characterization of connected subsets of shift-invariant measures $\add'\subset\add$ such that there exists a cellular automaton $F$ which verifies $\add(F,\mu)=\add$ and
$\add'(F,\mu)=\add'$ (Corollary~\ref{cor:ConvCesàroMeasureBis}).
 \item Rice theorem for shift-invariant measures and connected subsets of shift-invariant measures reached by a cellular automaton (Corollaries~\ref{cor:Rice}, \ref{cor:RiceSingle} and~\ref{cor:RiceCesaro}).
\end{itemize}

In Section~\ref{section:Oracle}, we consider the case where the set of limit points depends on the initial measure. Computational constraints appear to describe functions $\mu\longmapsto\add(F,\mu)$ that can be realized in this way. Indeed, it is possible to ``transfer'' the computational complexity of
the initial measure (using it as an oracle) to the set of limit points. Modifying the construction of Section~\ref{section:Construction}, we manage to build
a set of limit points depending on the density of a special state; however, we do not obtain a complete characterization.\\

In the Section~\ref{section:NoAux}, we carry the previous characterizations to the case where auxiliary states are not allowed, i.e., the cellular automaton can only use the same alphabet as the limit
measure(s). This is only possible, however, under some additional hypotheses on the support of the measures.

\section{Definitions}

\subsection{Configuration space and cellular automata}

Let $\A$ be a finite alphabet. Consider $\az$ the \define{space of configurations} which are $\Z$-indexed sequences in $\A$. If $\A$ is
endowed with the discrete topology, $\az$ is compact, perfect and totally disconnected in the product topology.
Moreover one can define a metric on $\az$ compatible with this topology:
\[\forall x,y\in\az,\quad \dc(x,y)=2^{-\min\{|i|: x_i\ne y_i \ i\in\Z \}}.\]

Let $\U\subset\Z$. For $x\in\az$, denote $x_{\U}\in\A^{\U}$ the restriction of $x$ to $\U$. Given a pattern
$w\in\A^{\U}$, one defines the cylinder $[w]_{\U}=\{x\in\az : x_{\U}=w\}$. Denote $\A^{\ast} = \bigcup_n\A^n$ the set of all \define{finite
words} $w=w_0\dots w_{n-1}$; $|w|=n$ is the \define{length} of $w$. Also denote $[w]_i=[w]_{[i,i+|w|-1]}$ and $[w]=[w]_0=[w]_{[0,|w|-1]}$.

The \define{shift} map $\s:\az\to\az$ is defined by $\s(x)_i=x_{i+1}$ for $x=(x_m)_{m\in\Z}\in\az$ and $i\in\Z$. It is an homeomorphism of $\az$. Let $w\in\A^{\ast}$, denote $x = \mathstrut^{\infty}w^{\infty}$ the \define{$\s$-periodic word} defined by $x_{[0,|w|-1]}=w$ and $\s^{i+|w|}(x)=\s^i(x)$ for all $i\in\Z$.

A \define{cellular automaton} (CA) is a pair $(\az,F)$ where $F:\az\to\az$ is  a continuous function that commutes with the shift ($\s^i\circ F=F\circ\s^i$ for all $i\in\Z$). By Hedlund's theorem, it is equivalent to a function defined by $F(x)_i=\overline{F}((x_{i+u})_{u\in\U_F})$ for all $x\in\az$ and $i\in\Z$, where $\U_F\subset\Z$ is a finite set named \define{neighborhood} and $\overline{F}:\A^{\U_F}\rightarrow\A$ is a \define{local rule}.

\subsection{\texorpdfstring{Sets of measures on $\az$}{Sets of measures on AZ}}

\subsubsection{Dynamical properties}
 Let $\Ba$ be the Borel sigma-algebra of $\az$. Denote by $\mathcal{M}(\az)$ the set of probability measures on $\az$
defined on the sigma-algebra $\Ba$. Let $\Ms(\az)$ be the \define{$\s$-invariant probability measures} on $\az$, that is to say the measures
$\mu\in\mathcal{M}(\az)$ such that $\mu(\s^{-1}(B))=\mu(B)$ for all $B\in\Ba$. Trivially, for a $\s$-invariant measure $\mu$, one has $\mu([u]_i)=\mu([u])$ for
all $i\in\Z$.

Usually $\Ms(\az)$ is endowed with \define{weak$^\ast$ topology}: a sequence $(\mu_n)_{n\in\N}$ of $\Ms(\az)$ converges to $\mu\in\Ms(\az)$ if and only if, for
all finite subsets $\U\subset\Z$ and for all patterns $u\in\A^{\U}$, one has $\lim_{n\to\infty}\mu_n([u]_{\U})=\mu([u]_{\U})$. In the weak$^{\ast}$ topology, the
set $\Ms(\az)$ is compact and metrizable. A metric is defined by \[\dm(\mu,\nu)=\sum_{n\in\N}\frac{1}{2^n}\max_{u\in\A^n}|\mu([u])-\nu([u])|.\]

Define the \define{ball} centered on $\mu\in\Ms(\az)$ of radius $\varepsilon >0$ as \[\Ball(\mu,\varepsilon)=\left\{\nu\in\Ms(\az) :
\dm(\mu,\nu)\leq\varepsilon \right\}.\]

A measure $\mu\in\Ms(\az)$ is \define{$\s$-ergodic} if for every $\s$-invariant borelian subset $B\in\Ba$ (that is to say $\s^{-1}(B)=B$ $\mu$-almost
everywhere), one has $\mu(B)=0$ or $1$. The set of $\s$-ergodic probability measures is denoted by $\Merg(\az)$. Of course $\Merg(\az)\subset\Ms(\az)$.

For $\U\subset\Z$ not necessarily finite, denote by $\Ba_{\U}$ the $\s$-algebra generated by the set $\{[u]_{\U}:u\in\A^{\U'}, \U'\underset{\textrm{finite}}{\subset}\U\}$.
Define the \define{weak mixing coefficients} of a measure $\mu\in\Ms(\az)$ as
\[\psi_{\mu}(n)=\sup\left\{\left|\frac{\mu(A\cap B)}{\mu(A)\mu(B)}-1\right| : A\in \Ba_{]-\infty,0]},\, B\in\Ba_{[n,\infty[},\, \mu(A)>0,\, \mu(B)>0\right\}.\]

A measure $\mu\in\Ms(\az)$ is $\mathbb{\psi}$\define{-mixing} if $\psi_{\mu}(n)\underset{n\to\infty}{\longrightarrow}0$. Denote $\Mpsimix(\az)$ the set of $\psi$-mixing measures,
of course $\Mpsimix(\az)\subset\Merg(\az)$.

For a measure $\mu\in\Ms(\az)$, define $\supp(\mu)$, the \define{support} of $\mu$, as the set of configurations of $\az$ such that any open neighborhood of these points have positive measure.
Denote $\Mergfull(\az)$ the set of ergodic measures with full support, and $\Mmixfull(\az)$ the set of $\psi$-mixing measures with full support.

\subsubsection{Classical examples}
Let $\lambda=(\lambda_a)\in[0;1]^\A$ such that $\sum_{a\in\A}\lambda_a=1$. The associated \define{Bernoulli measure} $\mu_{\lambda}$ is
defined by
\[\mu_{\lambda}([u_0\dots u_n])=\lambda_{u_0}\cdots\lambda_{u_n}\qquad\textrm{for all }u = u_0\dots u_n\in\A^{\ast}.\]

Let $x\in\az$. The \define{Dirac measure} supported by $x$ is defined by
\[\delta_x([u])=\begin{cases}0& \textrm{ if }x\notin[u]\\ 1 & \textrm{ if }x\in[u].\end{cases}\]

Generally $\delta_x$ is not $\s$-invariant. However, if $x$ is $\s$-periodic, it is possible to define the $\s$-invariant measure supported by $x$ taking the
mean of the measures $\delta_{\s^i(x)}$. Thus, for a word $w\in\A^{\ast}$, we define the \define{$\s$-invariant measure supported by $^{\infty}w^{\infty}$} by
\[\meas{w}=\frac1{|w|}\sum_{i\in[0,|w|-1]}\delta_{\s^i(\mathstrut^\infty w^\infty)}.\]

The set of measures $\left\{\meas{w}:w\in\A^{\ast}\right\}$ is dense in $\Ms(\az)$~\cite{Peteren-1983-livre}.

\subsubsection{Action of a cellular automaton on $\Ms(\az)$ and limit points}
Let $(\az,F)$ be a cellular automaton and $\mu\in\mes_{\s}(\az)$. Define the \define{image measure} $\F\mu$ by  $\F\mu(A)=\mu(F^{-1}(A))$ for all $A\in\Ba$.
Since $F$ is $\s$-invariant, that is to say $F\circ\s=\s\circ F$, one deduces that $\F\mu\in\Ms(\az)$. We consider the continuous application $\F:\Ms(\az)\to\Ms(\az)$. Moreover if $\mu\in\Merg(\az)$ then $\F\mu\in\Merg(\az)$.

We consider $(\F^t\mu)$ the \define{iteration of $F$ on $\mu$}, and its \define{Cesàro mean} at time $t\in\N$ defined by \[\varphi_t^F(\mu)=\frac{1}{t+1}\sum_{i=0}^t\F^i\mu\in\Ms(\az).\]

For a measure $\mu\in\Ms(\az)$, we are interested in the asymptotic behavior of the sequences $(\F^t\mu)_{t\in\N}$ and
$(\varphi_t^F\mu)_{t\in\N}$. Define $\add(F,\mu)$ the \define{set of cluster points} (or \textbf{limit points}) of the sequence $(F^t\mu)_{t\in\N}$ and $\add'(F,\mu)$ the \define{set of
cluster points of the sequence $(\varphi_t^F\mu)_{t\in\N}$}. Since $\Ms(\az)$ is compact, $\add(F,\mu)$ and $\add'(F,\mu)$ are nonempty. When $\add(F,\mu)$ is a singleton $\{\nu\}$, then $\F^t\mu([u])\underset{t\to\infty}{\longrightarrow}\nu([u])$. This corresponds to the intuitive notion of asymptotic behavior as observed in simulations.\\

Our main purpose is to characterize which sets of measures can be realised in this way.
There are topological obstructions for these sets: $\add(F,\mu)$ and $\add'(F,\mu)$ are closed and thus compact, and it is well known that
$\add'(F,\mu)$ is connected. There are also computability obstructions: we study in the next section the case where the initial measure is computable, and this will be generalized in Section~\ref{section:Oracle}.

\section{Computability obstructions}\label{section:ComputableObstruction}

\subsection{Notion of computability}\label{section:TuringMachine}

\begin{definition}A \define{Turing machine} $\mathcal{TM}=(Q,\Gamma,\#,q_0,\delta,Q_F)$ is defined by:
\begin{itemize}
\item $\Gamma$ a finite alphabet, with a blank symbol $\#\notin\Gamma$. Initially, a one-sided infinite memory tape is filled with $\#$, except for a finite prefix (the input), and a computing head is located on the first letter of the tape;
\item $Q$ the finite set of states of the head; $q_0\in Q$ is the initial state;
\item $\delta : Q\times\Gamma\to Q\times\Gamma\times\{\leftarrow,\cdot\,
,\rightarrow\}$ the transition function. Given the state of the head and the letter it reads on the tape --- depending on its position --- the head can change state, replace the letter and move by one cell at most.
\item $Q_F\subset Q$ the set of final states --- when a final state is
reached, the computation stops and the output is the value currently written on the tape.
\end{itemize}

A function $f : X\to Y$ with $X$ and $Y$ two enumerable sets is
\define{computable} if there exists a Turing machine that, up to reasonable encoding, stops and returns
$f(x)$ on any entry $x\in X$.
\end{definition}

\subsection{Measures and computability}\label{section:ComputableMeasure}

\begin{definition}
A measure $\mu\in\Ms(\az)$ is \define{computable} iff there exists $f:\A^{\ast}\times\N\to\Q$ computable such that \[|\mu([u])-f(u,n)|<2^{-n}.\]

A sequence of measures $(\mu_i)_{i\in\N}$ is \define{computable} iff there exists $f:\A^{\ast}\times\N\times \N\to\Q$ computable such that $|\mu_i([u])-f(u,n,i)|<2^{-n}.$ In particular all $\mu_i$ are computable.

A measure $\mu\in\Ms(\az)$ is \define{recursively computable} iff there exists an computable sequence of measures $(\mu_i)_{i\in\N}$ such that
$\lim_{i\to\infty}\mu_i=\mu$.
 Equivalently there exists $f:\A^{\ast}\times\N\to\Q$ computable such that \[|\mu([u])-f(u,n)|\underset{n\to\infty}{\longrightarrow}0.\]
\end{definition}

Denote $\Meff(\az)$ the set of computable measures and $\Mreff(\az)$ the set of recursively computable measures. Of course $\Meff(\az)\subset\Mreff(\az)$.
There exists an equivalent way to define these notions:

\begin{proposition}\label{prop:ApproximComputableMeasure}
A measure $\mu\in\Ms(\az)$ is computable if and only if there exists $f:\N\to\A^{\ast}$ computable such that $\dm\left(\mu,\meas{f(n)}\right)\leq 2^{-n}$ for
all $n\in\N$.

A measure $\mu\in\Ms(\az)$ is recursively computable if and only if there exists $f:\N\to\A^{\ast}$ computable such that
$\underset{n\to\infty}{\lim}\meas{f(n)}=\mu$.
\end{proposition}
\begin{proof}
Let $\mu\in\Meff(\az)$. Since the set $\left\{\meas{w}:w\in\A^{\ast}\right\}$ is dense in $\Ms(\az)$ and is enumerable, we enumerate
it until we find $w\in\A^{\ast}$ such that $|\mu([u])-\meas{w}([u])|<2^{-n-2}$ for all $u\in\A^k$ with $k\in[0,n+1]$. This is possible since $\mu$ is computable. One has
\[\dm(\mu,\meas{w})=\sum_{i\in\N}\frac{1}{2^i}\max_{u\in\A^i}|\mu([u])-\nu([u])|\leq \frac{1}{2^{n+1}}+\sum_{i\geq n+2}\frac{1}{2^i} \leq\frac{1}{2^n}.\]

 Let $\mu\in\Mreff(\az)$. There exists a computable sequence of measures $(\mu_i)_{i\in\N}$ such that $\lim_{i\to\infty}\mu_i=\mu$. By the previous point we get a word $f(n)\in\A^{\ast}$ such that $\dm(\mu_n,\meas{f(n)})\leq 2^{-n}$ for $n\in\N$. Clearly $f:\N\to\A^{\ast}$
is
computable and $\dm(\mu,\meas{f(n)})\leq \dm(\mu,\mu_n)+\dm(\mu_n,\meas{f(n)})\underset{n\to\infty}{\longrightarrow}0$.

In both cases, the reciprocal is obvious.
\end{proof}

The set of measures supported by periodic orbits is dense in $\Ms(\az)$. We will need a more precise statement
that the rate of convergence can be bounded by a computable sequence.

\begin{proposition}\label{prop:compperiodic}
 There is a computable sequence $\alpha_k \underset{k\to\infty}{\longrightarrow} 0$ such that for all $k\in\N$, one has \[\mes(\az) \subset \bigcup_{u\in \A^k}\B(\meas{u},\alpha_k).\]
\end{proposition}
In the following proof, all logarithms are in base $|\A|$.
\begin{proof}
 Take $\mu \in \mes(\az)$ and $n\in\N$. For each $w\in\A^n$, define $p_w \in \N$ such that $\left|p_w - \mu([w])\cdot |\A|^{3n}\right| < 1$ and
 $\sum_{w\in\A^n} p_w = |\A|^{3n}$. Now consider the following generalisation of
the de Bruijn digraph with multiedges and loops, noted $G = (V,E)$. The set of vertices $V$ is $\A^{n-1}$, and for all $u,v\in V$:
 \begin{itemize}
  \item if there are $a,b\in\A$ and $w\in\A^{n-2}$ such that $u = aw$ and $v = wb$, then there are $p_{awb}$ edges from $u$ to $v$ labeled $b$;
  \item otherwise, there are no edge from $u$ to $v$.
 \end{itemize}

Intuitively, from an Eulerian cycle in this graph we could build a periodic word where the frequency of each word $u \in\A^n$ is $\frac{p_u}{|\A|^{3n}}$;
however, this graph is not necessarily Eulerian.
We can turn it into an Eulerian graph by adding a small number of edges.

We denote $d^+(u)$, resp. $d^-(u)$ the outdegree, resp. indegree of the node $u$. By definition, $d^+(u) = \sum_{a\in\A}p_{au}$ so that
$|\mu([u])\cdot |\A|^{3n}-d^+(u)| \leq \sum_{a\in\A}|\mu([au])\cdot |\A|^{3n} - p_{au}| < |\A|$,
and similarly for $d^-(u)$. We note $I(u) = d^+(u)-d^-(u)$ the \define{imbalance} of the node $u$. Notice that $|I(u)|<2|\A|$ and $\sum_{u\in V}I(u) = 0$.

Suppose there exists $u,v \in V$ such that $I(u)<0,I(v)>0$. There is a sequence of vertices $u_0,\dots, u_i$ with $i\leq n-1$, $u_0=u$ and $u_i=v$, such that we can add a labeled edge between two successive vertices without breaking the edge condition defined above. By doing so we increse $I(u)$ by
one and decrease $I(v)$ by one without affecting other vertices. By repeating this operation, we bring the imbalance of every vertex to 0 with less than
$2(n-1)|\A|\cdot |\A|^{n-1}$
additional edges, that is, we get an Eulerian graph. Denote $G'$ this augmented graph and $p'_w$ the multiplicity of the edge corresponding to $w\in\A^n$.

From an Eulerian cycle in $G'$ we build a word $\pi$ such that $|\pi| = \sum_{w\in\A^n}p'_w \leq |\A|^{3n}+|\A|^{n+\log(2n)} < |\A|^{3n+1}$, and we consider
the measure supported by its periodic orbit.
For $w\in\A^n$, we have by construction $\meas{\pi}([w]) = \frac {p'_w}{\sum_{u\in\A^n}p'_u}$, so that:
\begin{align*}
\left|\meas{\pi}([w]) - \mu([w])\right| &\leq \left|\frac {p'_w}{\sum_{u\in\A^n}p'_u} - \frac {p_w}{|\A|^{3n}}\right|+ \left|\frac
{p_w}{|\A|^{3n}}-\mu([w])\right| \\
&\leq \frac1{|\A|^{3n}}\left[\left|\frac{|\A|^{3n}}{\sum_{u\in\A^n}p'_u}-1\right|p'_w+ \left|p'_w - p_w\right|+1\right]\\
&\leq \frac1{|\A|^{3n}}\left[|\A|^{\log(2n)-2n} p'_w + |\A|^{n+\log(2n)}+1\right]\\
&\leq \frac1{|\A|^{2n-\log(2n)}}
\end{align*}
and for any $k\leq n$, if we consider $w\in\A^k$, $|\meas{\pi}([w])-\mu([w])| \leq \frac1{|\A|^{n+k-\log(2n)}}$. Consequently:
\begin{align*}
d(\meas{\pi},\mu) &= \sum_{k\in\N}\max_{w\in\A^k}\frac{\meas{\pi}[w]-\mu([w])}{2^k} \\
&\leq \sum_{k=1}^n  \frac 1{2^k}\cdot\frac1{|\A|^{n+k-\log(2n)}} + \frac 1{2^n}\\
&\leq \frac1{|\A|^{n-\log(2n)}}
\end{align*}
and $|\pi| \leq |\A|^{3n+1}$. Since such a $\pi$ exists for
all $\mu$, we can choose $\alpha_k = |\A|^{-\left\lfloor\frac{\log k-1}3\right\rfloor+\log \left(2\left\lfloor\frac{\log k-1}3\right\rfloor\right)}$,
which is computable.
\end{proof}

\subsection{Action of a cellular automaton on computable measures}

\begin{proposition}\label{prop:OneStep}
Let $(\az,F)$ be a cellular automaton. If $\mu\in\Meff(\az)$ then $(\F^t\mu)_{t\in\N}$ is a computable sequence of measures. In particular, if $\F^t\mu\underset{t\to\infty}{\longrightarrow}\nu$ then $\nu\in\Mreff(\az)$.
\end{proposition}
\begin{proof}
Suppose $|\A| = 2$ to simplify the proof. By definition, there is a computable function $f:\A^{\ast}\times\N\to\Q$ such that $|\mu([u])-f(u,n)|\leq2^{-n}$. The function $F$ is defined locally; in particular, if $\U_F\subset[l,r]$, $F^t(x)_{[0,k]}$ depends only on $x_{[lt,rt+k]}$. In other words, for all $u\in\A^k$, there is a set $\mathbf{Pred}_t(u)\subset\A^{[lt,rt+k]}$ such that $F^{-t}([u])=\cup_{v\in\mathbf{Pred}_t(u)}[v]$.
Now consider the function \[f':(u,n,t)\mapsto \sum_{v\in\mathbf{Pred}_t(u)}f(v,2n+(r-l)t).\] It is computable by enumerating elements of $\A^{k+(r-l)t}$ and checking if $F^t([v]_{-lt})\subset [u]$ by iterating the local rule on $v$. Finally
\begin{align*}
|\F\mu([u])-f'(u,n,t)|&=\left|\mu\left(\bigcup_{v\in\mathbf{Pred}_t(u)}[v]\right) - \sum_{v\in\mathbf{Pred}_t(u)}f(v,2n+(r-l)t)\right| \\
&\leq \sum_{v\in\mathbf{Pred}_t(u)} \left|\mu([v]) - f(v,2n+(r-l)t)\right|\\
&\leq 2^{n+(r-l)t}\cdot 2^{-2n-(r-l)t} = 2^{-n}
\end{align*}
which means that $(\F^t\mu)_{t\in\N}$ is a computable sequence of measures.
\end{proof}

We wish to extend this computability obstruction to sets of limit points.

\subsection{Compact sets in computable analysis}\label{section:ComputableAnalysis}

We introduce computability notions on compact sets. This is a part of the theory of computable analysis on metric spaces for which a standard reference book is~\cite{Weihrauch-2000}.

In a metric space, a compact set $\add$ is characterized by the function $d_{\add}:\mu\mapsto\inf_{\nu\in\add}\dm(\nu,\mu)$. Thus the computability of a compact set
can be
defined by the computability of its distance function.

\begin{definition}\label{def:sigma2compact}
A sequence of functions $(f_n:\Ms(\az)\longrightarrow\R)_{n\in\N}$ is \define{computable} if
\begin{itemize}
\item there exists  $a:\N\times\N\times\A^{\ast}\longrightarrow\Q$ computable such that  $\left|f_n(\meas{w})-a(n,m,w)\right|\leq\frac{1}{m}$ for every
$w\in\A^{\ast}$ and $n,m\in\N$ (sequential computablity);
\item there exists $b:\N\longrightarrow\Q$  computable such that $\dm(\mu,\nu)<b(m)$ implies $\left|f_n(\mu)-f_n(\nu)\right|\leq\frac{1}{m}$ for all $n,m\in\N$
(computable uniform equicontinuity).
\end{itemize}

A function $f:\Ms(\az)\longrightarrow\R$ is \define{$\Sigma_2$-computable} if there exists a computable sequence of functions
$(f_n:\Ms(\az)\longrightarrow\R)_{n\in\N}$ such that $f=\underset{n\longrightarrow\infty}{\textrm{liminf}}\, f_n$.

A compact set $\add\subset\Ms(\az)$ is \define{$\Sigma_2$-computable} if $d_{\add}:\Ms(\az)\to\R$ is $\Sigma_2$-computable.
\end{definition}
If such a set is reduced to a singleton $\{\nu\}$ then $\nu\in\Mreff(\az)$ and reciprocally.

\begin{remark}
Classically a function $f:\Ms(\az)\longrightarrow\R$ is computable if it satisfies Definition~\ref{def:sigma2compact} without dependency on the index of the
sequence, and a compact set $\add\subset\Ms(\az)$ is computable if $d_{\add}$ is computable. In this case it is decidable whether a finite set of balls is a
cover of $\add$.

The name ``$\Sigma_2$-computable'' comes from an analogy with the real arithmetic hierarchy~\cite{Zheng-Weihrauch-2001,Ziegler-2005}
\end{remark}

\begin{proposition}\label{prop:add=s2ccc}
Let $(\az,F)$ be a cellular automaton and $\mu\in\Meff(\az)$. Then $\add(F,\mu)$ and $\add'(F,\mu)$ are $\Sigma_2$-computable compact sets.
\end{proposition}
\begin{proof}
 Let $f_n:\nu\mapsto\dm(\F^n\mu,\nu)$. Since $\mu$ is computable, $(f_n)_{n\in\N}$ is sequentially computable. Moreover
$|f_n(\nu)-f_n(\nu')|=|\dm(\F^n\mu,\nu)-\dm(\F^n\mu,\nu')|\leq\dm(\nu,\nu')$ so $(f_n)_{n\in\N}$ is computably uniformly continuous. The result follows from the fact
that $d_{\add(F,\mu)}(\nu)=\liminf_{n\to\infty}\dm(\F^n\mu,\nu)$.

The same reasoning holds for $\add'(F,\mu)$.
\end{proof}

\subsection{\texorpdfstring{Technical characterization of $\Sigma_2$-computable compact connected sets}{Technical characterization of Sigma2-computable compact connected sets}}

To realise a $\Sigma_2$-computable compact set of measures $\add$ by a cellular automaton, we need a recursive enumeration of words $(w_n)_{n\in\N}$ which
describes $\add$ in a certain way. However, the limit points of the construction presented in Section~\ref{section:Construction} are a connected set,
because it builds an infinite path composed of segments of the form $\left[\meas{u},\meas{v}\right]=\left\{t\meas{u}+(1-t)\meas{v}:t\in[0,1]\right\}\subset\Ms(\az)$ where
$u,v\in\A^{\ast}$. The following proposition describes how such connected sets can be covered by a polygonal path.

\begin{definition}
Let $(w_n)_{n\in\N}$ be a sequence of words of $A ^{\ast}$. Denote $\add((w_n)_{n\in\N})$ the \define{limit points of the polygonal path} defined by the sequence of measures
$(\meas{w_n})_{n\in\N}$ \[\add((w_n)_{n\in\N})=\bigcap_{N>0}\overline{\bigcup_{n\geq N}\left[\meas{ w_n},\meas{w_{n+1}}\right]}.\]

\end{definition}

\begin{proposition}\label{polygonalcover}
 Let $\add\subset\Ms(\B^\Z)$ be a non-empty $\Sigma_2$-computable, compact, connected set ($\Sigma_2$-CCC for short). Then there exists a computable sequence of words $(w_n)_{n\in\N}$ such that $\add =\add((w_n)_{n\in\N})$.
\end{proposition}

\begin{proof} By definition, there is a computable sequence of functions $(f_n)_{n\in\N}$ satisfying $d_\add = \liminf_{n\in\N} f_n$, and let
$a:\N\times\N\times\A^{\ast}\to\Q$ and  $b:\N\to\Q$ be the computable functions given by Definition~\ref{def:sigma2compact}. Define
$\A^{\leq k}=\bigcup_{i\leq k}\A^i$. Clearly $\A^{\leq k}\subset\A^{\leq k+1}$ and $\bigcup_{k\in\N}\{\meas{w}: w\in\A^{\leq k}\}$ is dense in
$\Ms(\A^\Z)$.

Now define $\mathbf{V}_k^t = \left\{w\in\A^{\leq k} : \exists t'\in[k,t] \textrm{ such that } a(t',t,w)<2\alpha_k\right\}$, where the computable sequence $(\alpha_k)_{k\in\N}$ is defined in
Proposition~\ref{prop:compperiodic}. For each $t$, we compute the elements of $\mathbf{V}_k^t$ for $k\leq t$ by increasing $k$. The  sequence $w_n$ is built algorithmically  in the
following way:

Suppose $w_0\dots w_n$ have already been computed and we begin to compute $\mathbf{V}_k^t$ for $k\leq t$. When an element $w$ of $\mathbf{V}_k^t$ that was not in $\mathbf{V}_k^{t-1}$
is computed, we want to add it to the sequence. Let $i\in[0,k]$ be the maximal value such that $\bigcup_{u\in\mathbf{V}_i^t}\Ball(\meas{u},\alpha_i)$ has a connected
component containing $\meas{w_n}$ and $\meas{w}$. We can find with a simple graph algorithm a sequence $u_0,\dots,u_j\in\mathbf{V}_i^t$ such that the
path $[\meas{w_n},\meas{u_0}]\cup\dots \cup[\meas{u_j},\meas{w}]$ is included in it. The words $u_0,\dots, u_j, w$ are added to the sequence
$(w_i)_{i\in[0,n]}$.

Now we will prove the correctness of this algorithm.

\Claim{
 If $\mu\in\add$, then $\mu\in \add((w_n)_{n\in\N})$
}

\bclaimprf
There is a sequence of words $(u_n)_{n\in\N}$ such that $\dm(\meas{u_n},\mu)<\alpha_n$. Since $d_\add(\meas{u_n})<\alpha_n$, there is a $t>|u_n|$ such that
$f_{t}(\meas{u_n})<\frac{3}{2}\alpha_n$. Let $t_n>t$ satisfying $\frac{1}{t_n}\leq\frac{\alpha_n}{2}$. Then $a(t,t_n,u_n)\leq
f_{t}(\meas{u_n})+\frac{1}{t_n}\leq 2\alpha_k$, which means that each $u_n$ is in $\mathbf{V}_{|u_n|}^{t_n}$, and by construction it appears at some point in the sequence
$(w_n)_{n\in\N}$.
\eclaimprf

\Claim{
 $\forall k, \exists T_k, \forall t>T_k, \mathbf{V}_k^t = \mathbf{V}_k^{T_k}$. Furthermore, we have $\add \subset \bigcup_{u \in \mathbf{V}_k^{T_k}}\Ball(\meas{u}, \alpha_k)$.
}

\bclaimprf
For all $k$, $\mathbf{V}_k^t$ is a discrete increasing bounded sequence (in the inclusion sense), so it is stationary. For each element $\mu\in\add$ there is an element
$u_k\in\A^{\leq k}$ such that $\dm(\mu,\meas{u_k})\leq \alpha_k$, and therefore $d_\add(\meas{u_k})\leq \alpha_k$. Consequently, $u_k\in\mathbf{V}_k^t$ for $t$ large enough.
\eclaimprf

\Claim{
 Let $u,v\in\A^{\leq k}$. If $d_\add(\meas{u})<\alpha_k$, $d_\add(\meas{v})<\alpha_k$, then one can find a path $u=u_0,u_1,\dots,u_{j-1},u_j=v\in\mathbf{V}_k^{T_k}$ such that
$\bigcup_{i\in [0,j-1]}[\meas{u_i},\meas{u_{i+1}}]\subset \left\{\mu:d_{\add}(\mu)\leq\alpha_k\right\}.$
}

\bclaimprf
One has  $u,v\in\mathbf{V}_k^{T_k}$. Let $\nu,\nu'\in\add$ be such that $d(\meas{u},\nu)\leq\alpha_k$ and $d(\meas{v},\nu')\leq\alpha_k$. By Claim 2,
$\bigcup_{u\in\mathbf{V}_k^{T_k}}\Ball(\meas{u},\alpha_k)$ contains $\add$, which is connected, so there is a path from $\nu$ to $\nu'$ in
$\bigcup_{u\in\mathbf{V}_n^{T_k}}\Ball(u,\alpha_k)$. Thus there exists $u_0,\dots,u_j\in\mathbf{V}_k^{T_k}$ such that $u_0=u$, $u_j=v$,
$\dm(\meas{u_i},\meas{u_{i+1}})<\alpha_k$ and $d_{\add}(\meas{u_i})<\alpha_k$ for $i\in[0,j-1]$.   Finally, \[\bigcup_{i\in
[0,j-1]}[\meas{u_i},\meas{u_{i+1}}]\subset \left\{\mu:d_{\add}(\mu)\leq\alpha_k\right\}.\] \eclaimprf

\Claim{$\forall \varepsilon>0, \exists n_{\varepsilon}, \forall n>n_\varepsilon$, we have $\forall \mu\in\Ms(\az), d_{\add}(\mu)>3\varepsilon \Rightarrow
f_n(\mu)>\varepsilon$.}
\bclaimprf
 Let $\mu \in \Ms(\az)$ such that $d_\add(\mu)\geq 3\varepsilon$. $\exists n_\varepsilon(\mu), \forall n\geq n_\varepsilon(\mu), f_n(\mu)>2\varepsilon$. By taking
$k_\varepsilon\in\N$ such that $\frac 1{k_\varepsilon}<\varepsilon$, we have by computable uniform equicontinuity of $(f_n)_{n\in\N}$ $f_n(\nu)>\varepsilon$
for all $\nu\in\Ball(\mu, b(k_\varepsilon))$ and all $n\geq n_\varepsilon(\mu)$.

Since $\{\mu\in\Ms(\az) : d_\add(\mu)\geq3\varepsilon\}$ is compact, we can cover it with a finite number of balls of radius $b(k_\varepsilon)$, and we define
$n_\varepsilon$ the maximum value of $n_\varepsilon(\mu)$ on ball centers. Thus, $\forall n>n_\varepsilon, \forall \mu\in\Ms(\az), d_{\add}(\mu)>3\varepsilon
\Rightarrow f_n(\mu)>\varepsilon$.
\eclaimprf

\Claim{
 If $\mu\not\in\add$, then $\mu\not\in \add((w_n)_{n\in\N})$.
}
\bclaimprf
Let $\mu\not\in\add$ and consider $\varepsilon>0$ such that $2\varepsilon<d_{\add}(\mu)$. Take $k'$ large enough such that $\alpha_{k'} < \varepsilon$, and $k$ large
enough such that $9\alpha_k < \alpha_{k'}$. Denote $n_{3\alpha_k}$ the integer obtained in Claim 4.

Take $t>\max(T_k,\frac{1}{\alpha_k},n_{3\alpha_k})$, and let $w$ be a word added by the algorithm in the sequence $(w_n)_{n\in\N}$ after time $t$. Since
$t>T_k$, there exists
$t'\in[|w|,t]$ such that $a(t',t,w)<2\alpha_k$. Thus one has $f_{t'}(\meas w)\leq 2\alpha_k+\frac 1t\leq 3\alpha_k$. Since $t\geq n_{3\alpha_k}$, by
Claim 4 we deduce that $d_{\add}(\meas{w})\leq 9\alpha_k \leq\varepsilon$. Since $t\geq T_{k}\geq T_{k'}$, by Claim 3, all paths added in order to reach $w$ are
in $\left\{\mu:d_{\add}(\mu)\leq\alpha_k\right\}$. Thus, for $N\in\N$ large enough: \[\B(\mu,\varepsilon)\cap \overline{\bigcup_{n\geq
N}\left[\meas{w_n},\meas{w_{n+1}}\right]}=\emptyset.\]
which means that $\mu\not\in \add((w_n)_{n\in\N})$. \eclaimprf
\end{proof}

\section{Construction of a cellular automaton realising a given set of measures}\label{section:Construction}

We want to prove a reciprocal to Proposition~\ref{prop:OneStep} and a partial reciprocal to Proposition~\ref{prop:add=s2ccc} using Proposition~\ref{polygonalcover}. Given a computable sequence of words $(w_n)_{n\in\N}$
in $\B^{\ast}$, we construct a cellular automaton realising $\add((w_n)_{n\in\N})$ as its set of limit points.

\begin{theorem}\label{MainTheorem}
Let $(w_n)_{n\in\N}$ be a computable sequence of words of $\B^{\ast}$, where $\B$ is a finite alphabet. Then there is a finite alphabet $\A\supset \B$ and a
cellular automaton $F : \A^{\Z}\to \A^{\Z}$ such that:
\begin{itemize}
 \item for any measure $\mu \in \Mmixfull(\A^\Z)$, $\add(F,\mu) = \add((w_n)_{n\in\N})$.
 \item if $\add((w_n)_{n\in\N})=\{\nu\}$, then for any measure $\mu \in \Mergfull(\A^\Z)$, $\F^t\mu\underset{t\to\infty}\longrightarrow \nu$.
\end{itemize}
\end{theorem}
Furthermore we get an explicit bound for the convergence rate in the first point of the theorem:
 \[\dm(\F^t\mu,\add((w_n)_{n\in\N})\leq O\left(\frac{1}{\log(t)}\right)+\sup\left\{\dm(\nu,\add((w_n)_{n\in\N})):\nu\in\bigcup_{n\geq n(t)}[\meas{w_n},\meas{w_{n+1}}]\right\},\]
where $n(t)=\Theta(\log(t)^2)$ and assuming that $w_n$ is computable in space $\sqrt{n}$.

In the rest of the section, we detail the construction of this cellular automaton and prove this theorem.

\subsection{Sketch of the construction}

In this section, we present the general framework to build the alphabet $\A$ and the cellular automaton $F$. Our goal is to compute each $w_n$ successively and write concatenated copies of it on the whole configuration. $\A$ contains a symbol $\hspace{-0.1cm$
(for \define{wall}) persisting in time, except under special circumstances; the idea is that to the left of each wall there is a small computing area where
$w_n$ is computed, and then it is copied repeatedly to its left until the next wall.

A main issue is to initialize the computing synchronously for each wall, even though we have no control over what cells appear at time 0. To do this,
we define another symbol $\hspace{-0.1cm$ (\define{init}), which appears only in the initial configuration, creating a wall while erasing the contents of neighboring cells and
initializing computation on its left. The resulting wall is said to be \define{initialized}.

\begin{definition}
 Let $x\in\az$. $[i,j]$ is a \define{segment at time 0} if $x_i$ and $x_j$ are two consecutive $\hspace{-0.1cm$ symbols, and a \define{segment at time $t$} if
$F^t(x)_i$
and $F^t(x)_j$ are two consecutive initialized walls $\hspace{-0.1cm$. Define the \define{length} of this segment as $i-j-1$.
\end{definition}

In all the paper, $t$ is the current time and $(T_n) \in \N^\N$ an increasing sequence of times that will be fixed later. Intuitively, $T_n$ is the time when each machine has computed $w_n$ and starts copying it in its left segment.

Since we have no control over the initial contents of each segment, we want to destroy non-initialized walls to guarantee that synchroneous
computing takes place everywhere.

To do that, we use the following method which is represented in Figure~\ref{figure:initialization}. On its left, each initialized wall keeps the value of current time under the form of a binary counter incrementing at
each step (\define{time counter}), and sends another incrementing counter to its right progressing at speed one (\define{sweeping counter}). Time and sweeping
counters already present in the initial configuration (not initialized) have a positive value, whereas those created by an $\hspace{-0.1cm$ symbol (initialized) have
value 0 at time 1, and they increment at the same rate. Thus, non initialized walls have older time counters, and by comparing time counters and sweeping counters as they meet, we can erase older counters and non-initialized walls as well.

\begin{figure}[!h]
\begin{center}
 \begin{tikzpicture}
 \fill[black!20!white] (-3,0) rectangle (11,6);

 \foreach \a in {0,8}
   {
   \fill[white] (\a,0) -- (\a+4,3) -- (\a+4,6.05) -- (\a,6.05) -- cycle;
   \fill[white] (\a,0) -- (\a-.5,0) arc (270:180:1.5 and 6.05) -- (\a,6.05) -- cycle;
   \draw[black, very thick] (\a,0) -- (\a,6);
   \draw[blue, thick] (\a,0) arc (270:190:1.5 and 7.25);
   \fill[blue, pattern = north east lines] (\a,0) arc (270:190:1.5 and 7.25) -- (\a,6) -- cycle;
   \filldraw[fill=white] (\a-0.17,-0.17) rectangle (\a+0.17,0.17);
   \draw (\a,0) node {\small $I$};
   }
\filldraw[fill=white] (8.3,-0.17) rectangle (8.64,0.17);
\draw (8.47,0) node {\small $I$};
\draw (7.7, -0.3) rectangle (8.77,0.3);
\draw (8.47,-0.5) node {\small{see section~\ref{section:bootstrapping}}};
\fill[white] (2.55,4.09) -- (5.21, 6.05) -- (2.55,6.05) -- cycle;
\draw[red,thick] (0.2,0.15) -- (4,3) -- (2.55,4.09) -- (5.21, 6);
\draw[red,thick] (8.2,0.15) -- (11,2.25);
\draw[red,thick] (6,0) -- (8,1.5) -- (6.9,2.325);
\fill[blue, pattern = north east lines] (4,0) -- (3.5,0) arc (240:185:2.2 and 7.7) -- (4,5.11) -- cycle;
\draw[blue, thick] (3.5,0) arc (240:185:2.2 and 7.7);
\draw[black, very thick] (4,0) -- (4,5.11);

\draw (-1.4,-0.5) rectangle (1.4,2.3);
\draw (-1.8,0.9) node {\rotatebox{90}{\small{Figure~\ref{figure:time} and \ref{figure:sweeping}}}};

\draw (2,2.4) rectangle (4.8,5.2);
\draw (1.7,3.8) node {\rotatebox{90}{\small{Figure~\ref{figure:comp1}}}};

\draw (6,0.6) rectangle (8.4,3);
\draw (5.7,1.8) node {\rotatebox{90}{\small{Figure~\ref{figure:comp2}}}};

 \end{tikzpicture}
\end{center}
\caption{Sketch of the bootstrapping and sweeping processes. Vertical lines are walls. White areas and grey areas are swept and non-swept, respectively. Dashed parts contain time counters (section \ref{section:time}) and Turing
machines (section \ref{section:computation}). Slanted lines are sweeping counters (section \ref{section:sweeping}).}\label{figure:initialization}
\end{figure}

In order to enlarge computational space and decrease the density of auxiliary states, segments of length $n$ are merged with their left neighbour at time $T_n$.
To determine the length of its right segment, each wall sends a signal to the right that bounces off the next wall and counts the return time. The Figure~\ref{figure:CopyMerge} is an overview of copy and merging processes.

\begin{figure}[!ht]
\begin{center}
 \begin{tikzpicture}
\fill[black!20!white] (8,0) -- (8,1) -- (5,4) -- (5,1) -- (3.5,2.5) -- (3.5,1) --
(2,2.5) -- (2,1) -- (0,3) -- (0,1) -- (-1,2) -- (-1,1) -- (-1,0) -- cycle;
\fill[black!20!white] (8,5) -- (6.5,6.5) -- (8,6.5) -- cycle (5,5) -- (3.5,6.5) -- (5,6.5) -- cycle
(0,5) -- (-1,6) -- (-1,6.5) -- (0,6.5) -- cycle;
\foreach \a/\b in {0/6.5,2/5,3.5/5,5/6.5,8/6.5}
   {
   \draw[black, very thick] (\a,0) -- (\a,\b);
   }
\draw[red,very thick] (2,1) -- (0,3) (3.5,1) -- (2,2.5) (5,1) -- (3.5,2.5) (8,1) -- (5,4)
(0,1) -- (-1,2) (0,5) -- (-1,6) (5,5) -- (3.5,6.5) (8,5) -- (6.5,6.5);
\draw[dotted,very thick] (0,1) -- (2,3) -- (0,5) (2,1) -- (3.5,2.5) -- (2,4) (3.5,1) -- (5,2.5) -- (3.5,4) (5,1) -- (8,4) -- (6,6) (5,5) -- (6.5,6.5);

\draw (1.75,4) rectangle (2,4.25);
\draw (1.875,4.1) node {\tiny M};
\draw[->, dotted] (1.875,4.25) -- (1.875,4.7);
\draw (1.75,4.75) rectangle (2,5);
\draw (1.875,4.85) node {\tiny M};

\draw (3.25,4) rectangle (3.5,4.25);
\draw (3.375,4.1) node {\tiny M};
\draw[->, dotted] (3.375,4.25) -- (3.375,4.7);
\draw (3.25,4.75) rectangle (3.5,5);
\draw (3.375,4.85) node {\tiny M};

\draw[<->] (3.5,0.2) -- (5,0.2);
\draw (4.25,-0.2) node {$n$};
\draw[->] (-1,-0.5) -- (-1,7);
\draw (-1,7.5) node {time};
\draw (-1.5,1) node {$T_{n-1}$};
\draw (-1.4,5) node {$T_n$};
\draw (-1.1,1) -- (-0.9,1) (-1.1,5) -- (-0.9,5);
\draw[dotted] (-1,1) -- (9,1) (-1,5) -- (9,5);

\draw (0.9,0.9) rectangle (4,4);
\draw (2.55,4.2) node {\small{Figure~\ref{figure:merge}}};

\draw (6.4,0.6) rectangle (8.4,2.6);
\draw (7.4,2.8) node {\small{Figure~\ref{figure:copy}}};

\draw (5.4,5.2) rectangle (6.8,6.6);
\draw (6.1,7.2) node {\footnotesize{Newer merging signals}};
\draw (6.1,6.85) node {\footnotesize{erase older signals}};

 \end{tikzpicture}
\end{center}
\caption{Sketch of the copying and merging processes. We suppose all walls are initialized. Slanted thick lines are copy processes (see section
\ref{section:copy}), slanted dotted lines are merging signals (see section \ref{section:merge}).}\label{figure:CopyMerge}
\end{figure}

Thus the considered alphabet consists in different layers $\A = \left\{\hspace{-0.1cm, \hspace{-0.1cm\right\}  \cup \alph{output}  \times \alph{comp}
\times \alph{time} \times \alph{sweeping} \times \alph{copy} \times \alph{merge}$, where:
\begin{itemize}
 \item $\hspace{-0.1cm$ and $\hspace{-0.1cm$ are the two above-mentioned symbols;
 \item $\alph{output} = \B\cup \{\#\}$ is the layer on which $w_n$ is output and then recopied;
 \item $\alph{comp}$ is the layer where computing takes place by simulating Turing machines;
 \item $\alph{time}$ is the layer on which time counters are incremented;
 \item $\alph{sweeping}$ is the layer on which sweeping counters move and are incremented, and where comparisons are done;
 \item $\alph{copy}$ is an auxiliary layer used in the process of writing copy the output;
 \item $\alph{merge}$ is an auxiliary layer used in the process of merging two segments.
\end{itemize}

All those alphabets contain a symbol $\#$ (blank) representing the absence of information. If $u \in \A$, note $output(u)$, resp. $comp(u),\ time(u)$\dots the projections on each layer (the result being $\#$ on $\hspace{-0.1cm$ and
$\hspace{-0.1cm$). We have $\B \subset \A$ up to the identification $b \mapsto (b, \#, \#, \#, \#, \#)$.\\

We shall detail the different alphabets in the following sections. As we will see, our construction needs interactions at a distance at most three, so we can
take $\U_F = \{-3,\dots,3\}$ as the neighbourhood of $\overline{F}$.

\subsection{Formatting the segments}

\subsubsection{Bootstrapping}\label{section:bootstrapping}
If two symbols $\hspace{-0.1cm$ are separated by two cells or less, the rightmost one is destroyed. Otherwise, any
$\hspace{-0.1cm$ symbol turns into a $\hspace{-0.1cm$, erasing the contents of three cells to its right and left (including walls), initializing on its left a computation and a time counter, and on its right a sweeping counter. No more $\hspace{-0.1cm$ or $\hspace{-0.1cm$ symbols can be created.\\

Walls, counters and computing areas created in this way are \define{initialized}, by opposition to those already present at time 0.
Walls persist over time and are only destroyed under two circumstances:
\begin{itemize}
 \item when it is in a situation such that it is impossible that it is initialized (e.g. without a time counter to its left);
 \item at time $T_n$, if it is the left bound of a segment of length $n$.
\end{itemize}

If a segment is of length three at time 0, then the time counter of the rightmost wall is erased at time 1 and the wall itself is destroyed at time 2. Thus segments have minimum length four from time 2 onwards.

\subsubsection{Counters}
All counters are binary in a redundant basis, so that they can be incremented by one at each step (keeping track of current time) in a local manner.

\begin{definition}[Redundant binary]
 Let $u = u_{n-1}\dots u_0 \in \{0,1,2\}^*$. The {\bf value} of $u$ is \[val(u) = \sum_{i=1}^n u_{i}2^i.\]Since the basis is redundant, different counters can
have the same value.
\end{definition}
\begin{definition}[Incrementation]\label{definition:incrementation}
 The incrementation operation $inc : \{0,1,2\}^*\mapsto \{0,1,2\}^*$ is defined in the following way. If $u_{|u|-1} = 2$, then $|inc(u)| = |u|+1$, $|u|$
otherwise, and:
\[inc(u)_i = \left\{
\begin{array}{ll}
1&\tx{si }i=|u|+1\tx{ and } u_{|u|-1} = 2;\\
u_i \mod 2 +1 & \tx{if }i=0\tx{ or } u_{i-1} = 2;\\
u_i \mod 2 & \tx{otherwise.}
\end{array}
\right.\]
\end{definition}

Intuitively,  the counter is increased by one at the rightmost bit and $2$ behaves as a carry propagating along the counter. When the leftmost bit is a carry, the length of the counter is increased by one. Thus:
\begin{fact}
 $val(inc(u)) = val(u)+1$.
\end{fact}

This operation is defined locally and can be seen as the local rule of a cellular automaton.

\subsubsection{Time}\label{section:time}
We use the alphabet $\alph{time} = \{0,1,2,\#\}$. In a configuration, a time counter is a word of maximal length containing no $\#$ in the time layer.
A time counter is \define{attached} if it is bounded on its right by a wall $\hspace{-0.1cm$, \define{detached} otherwise. \\

\begin{figure}[!ht]
\begin{center}
 \begin{tikzpicture}

\foreach \x\y\a in
{0/1/?,0/2/?,0/3/?,0/4/\#,0/9/\#,0/10/?,1/2/\#,1/3/\#,1/4/?,1/5/\#,1/9/\#,1/10/\#,2/2/\#,2/3/\#,2/4/\#,2/5/\#,2/6/\#,2/10/\#,3/2/\#,3/3/\#,3/4/\#,3/5/\#,
3/6/\#,3/7/\#,3/10/\#,4/3/\#,4/4/\#,4/5/\#,4/6/\#,4/7/\#,4/8/\#,4/10/\#,5/3/\#,5/4/\#,5/5/\#,5/6/\#,5/7/\#,5/8/\#,5/9/\#,5/10/\#,6/3/\#,6/4/\#,6/5/\#,6/6/\#,
6/7/\#,6/8/\#,6/9/\#,6/10/\#,7/4/\#,7/5/\#,7/6/\#,7/7/\#,7/8/\#,7/9/\#,7/10/\#}
  {
  \draw[dotted](-0.8*\y,0.8*\x) rectangle (-0.8*\y +0.8,0.8*\x +0.8);
  \draw(-0.8*\y+0.4,0.8*\x+0.4) node {\a};
  }

  \draw (0.4,0.4) node {I};
  \foreach \x in {1,...,7}
  {
  \filldraw[fill = black!50!white] (0,0.8*\x) rectangle (0.8,0.8*\x+0.8);
  \draw (0.4,0.8*\x+0.4) node {W};
  }
  \foreach \x\y\a in
{1/1/0,7/2/0,2/1/1,4/1/1,6/1/1,4/2/1,5/2/1,7/3/1,3/1/2,5/1/2,7/1/2,6/2/2,0/5/1,0/6/0,0/7/2,0/8/1,1/6/0,1/7/0,1/8/2,2/7/0,2/8/0,2/9/1,3/8/0,3/9/1,4/9/1}
  {
  \draw[very thick] (-0.8*\y,0.8*\x) rectangle (-0.8*\y +0.8,0.8*\x +0.8);
  \draw (-0.8*\y+0.4,0.8*\x+0.4) node {$\a$};
  }
  \draw [very thick] (0,0) rectangle (0.8,0.8);
 \end{tikzpicture}
  \caption{A detached time counter, and a time counter attached to an initialized wall. Only the layer $\alph{time}$ is represented. ? cells have arbitrary values.}
\label{figure:time}
 \end{center}
\end{figure}

At each step, attached counters are incremented by one while detached counters have their rightmost bit deleted (see Figure~\ref{figure:time}). Indeed, detached counters cannot be initialized
and can be safely deleted. Formally,
\begin{itemize}
 \item if $u_1 = \hspace{-0.1cm$, then $time(F(u)_0)= time(u_0)\mod 2 +1$;
 \item if $time(u_1) = \#$, then $time(F(u)_0)=\#$;
 \item otherwise, follow the incrementation definition (Definition~\ref{definition:incrementation}).
\end{itemize}

When a counter increases in length, it can erase a wall. However, this is not a problem, as we shall see in
Facts~\ref{fact:detached} and \ref{fact:attached}.

\begin{fact}\label{fact:detached}
 An initialized wall cannot be erased by a detached time counter.
\end{fact}

\begin{proof} A detached counter is not incremented and can extend by one cell at most because of the carries initially present in the word. But $\hspace{-0.1cm$
symbols
erase two cells to their right at initialization.
\end{proof}

\begin{fact}\label{Time}
 Each attached time counter $u$ in $F^t(a)$ satisfies $val(u)\geq t-1$, the equality being attained if this counter is attached to an initialized wall.
\end{fact}

\begin{proof} No time counter is created except at $t=1$ (by $\hspace{-0.1cm$). Therefore such a counter was present either in the initial configuration (with a nonnegative value),
or was created at $t=1$ by a $\hspace{-0.1cm$ symbol. It is incremented by one at each step in both cases.
\end{proof}

Thus we can use time counters to tell apart initialized walls from non-initialized walls, which will be the object of the next section.

\subsubsection{Sweeping and comparisons}\label{section:sweeping}
Sweeping counters are defined and incremented at each step in a similar way as time counters, but they have a range of different behaviors. The alphabet
$\alph{sweeping}$ is decomposed into two layers $\alph{state}$ and $\alph{value}$. A sweeping counter is a word of maximal length of state different than $\#$.
The possible states of the counter are:
\begin{description}
 \item[``Go'' state] The counter progresses at speed one to the right.
 \item[``Stop'' state] Once a wall is encountered, the counter progressively (right to left) stops.
 \item[``Comparison'' states] Once the whole counter has stopped, we locally compare the sweeping counter and the time counter, left to right, with a method we
will describe later.
\end{description}
The wall is destroyed if the sweeping counter is strictly younger, and the sweeping counter is destroyed otherwise (see Figures~\ref{figure:comp1} and
\ref{figure:comp2}).
In the former case, the counter progressively comes back to the ``Go'' state. \\

\begin{figure}[!ht]
\begin{center}
 \begin{tikzpicture}
  \draw (0.4,0.4) node {I};

  \foreach \x in {1,...,7}
  {
  \filldraw[fill = black!50!white] (0,0.8*\x) rectangle (0.8,0.8*\x+0.8);
  \draw (0.4,0.8*\x+0.4) node {W};
  }
  \foreach \x/\y/\a in {1/1/0,7/5/0,2/2/1,4/2/1,6/6/1,4/4/1,5/3/1,7/3/1,3/3/2,7/7/2,6/4/2,5/5/2,4/3/\#,5/4/\#,6/5/\#,7/4/\#,7/6/\#,0/3/1,0/4/\#,0/5/1,0/6/0,
  1/4/1,1/5/\#,1/6/2,2/5/2,2/6/\#,2/7/1,3/6/0,3/7/\#,3/8/2,4/7/1,4/8/\#,5/8/1}
  {
  \draw[very thick] (0.8*\y,0.8*\x) rectangle (0.8*\y +0.8,0.8*\x +0.8);
  \draw (0.8*\y+0.4,0.8*\x+0.6) node {$Go$};
  \draw[dotted] (0.8*\y,0.8*\x+0.4) -- (0.8*\y+0.8,0.8*\x+0.4);
  \draw (0.8*\y+0.4,0.8*\x+0.2) node {$\a$};
  }
  \draw [very thick] (0,0) rectangle (0.8,0.8);

\foreach \x/\y in {2/1,3/2,4/1,5/2,6/3,7/2}
  {
 \foreach \t in {1,...,\y}
  {
  \draw[dotted](0.8*\t,0.8*\x) rectangle (0.8*\t +0.8,0.8*\x +0.8);
  \draw(0.8*\t+0.4,0.8*\x+0.4) node {\#};
  }
  }

\foreach \x\y in {0/7,1/7,2/8,7/8}
\foreach \t in {\y,...,8}
{\draw[dotted](0.8*\t,0.8*\x) rectangle (0.8*\t +0.8,0.8*\x +0.8);
  \draw(0.8*\t+0.4,0.8*\x+0.4) node {\#};
}

\foreach \x in {1,...,6}
{
 \draw[dotted](0.8*\x+1.6,0.8*\x) rectangle (0.8*\x +2.4,0.8*\x +0.8);
 \draw(0.8*\x+2,0.8*\x+0.4) node {\#};
 \draw[dotted](0.8*\x+0.8,0.8*\x) rectangle (0.8*\x +1.6,0.8*\x +0.8);
 \draw(0.8*\x+1.2,0.8*\x+0.4) node {\#};
}

 \draw[dotted](1.6,0) rectangle (2.4,0.8);
 \draw(2,0.4) node {?};
 \draw[dotted](0.8,0) rectangle (1.6,0.8);
 \draw(1.2,0.4) node {?};
 \draw (8,3) rectangle (8.8,3.4) rectangle (8,3.8);
\draw[->,dotted] (10,3.2) node {\small{value}} (9.5,3.2) -- (9,3.2);
\draw[->,dotted] (10,3.6) node {\small{state}} (9.5,3.6) -- (9,3.6);
 \draw(4.65,3.05) node {{\footnotesize X}};
 \draw(3.85,3.05) node {{\footnotesize X}};

\end{tikzpicture}
\caption{One initialized and one uninitialized sweeping counter.
X symbols mark the cells where values are prevented to appear to avoid merging: the right counter is dominated. Only the layer $\alph{sweeping}$ is represented.}

\label{figure:sweeping}
 \end{center}
\end{figure}

Changing state takes some time to propagate the information along the counter. Therefore, counters passing from a ``Go'' state to a ``Stop'' state are
temporarily in a situation where the left part of the counter progresses whereas the right part does not. To avoid erasing information, counters in a ``Go''
state have \define{buffers}, i.e. the value of the counter is only written on half the cells, the other being erased when changing state (see
Figure~\ref{figure:sweeping}).\\

When its length increase, a counter will never merge with another counter, instead erasing bits from the right-hand counter to avoid merging: we say the right-hand
counter is {\bf dominated}. Notice that it is impossible for a counter located at the right of another counter to be initialized, and so it is safe to erase
bits of it.

\begin{fact}
 Any non-dominated sweeping counter $u$ of $F^t(x)$ satisfies $val(u)\geq t-1$, the equality being attained if the counter is initialized (from a $\hspace{-0.1cm$ symbol).
\end{fact}
\begin{proof} Similar to Fact~\ref{Time}.
\end{proof}

Thus, we guarantee that an initialized (hence non-dominated) sweeping counter is strictly younger than any non-initialized wall, and symmetrically. As for dominated counters, whose value is arbitrary, we will see that they are erased before any comparison takes place.

\begin{definition}[Comparison method]
 Let $u=u_0u_1\dots $ and $v = v_0v_1\dots$ be two counters in redundant binary basis (adding zeroes so that $|u| = |v|$). Let us note $sign(u-v)$ the
result of the comparison
between $u$ and $v$, that is, $+, 0$ or $-$.
\begin{description}
 \item[Case 1] if $|u| = |v| = 1$, $sign(u-v) = sign(u_0-v_0)$;
 \item[Case 2] if $u_0+\lfloor u_1/2\rfloor > v_0+\lfloor v_1/2\rfloor$, then $sign(u-v) = +$,\\ and symmetrically;
 \item[Case 3] if $u_0+\lfloor u_1/2\rfloor = v_0+\lfloor v_1/2\rfloor$, then $sign(u-v) = sign(u_1' u_2\dots - v_1'v_2\dots)$,\\
       where $u_1' = u_1 \mod 2$ and $v_1'=v_1 \mod 2$.
\end{description}
\end{definition}
In other words, we do a bit-by-bit comparison starting from the leftmost bit, considering that $\# = 0$, and taking into account the carry propagation ``in
advance'', so that the incrementation and carry propagation can continue during the comparison.
If the result can be determined locally (cases 1 and 2), the state is changed to $+$ or $-$, and it will propagate to the right along the counter. Otherwise
(case 3), the state changes to =, which means future bit comparisons will decide the result in the same way (see Figure \ref{figure:comp2}).\\

\begin{figure}[!ht]
\begin{center}
 \begin{tikzpicture}[scale=1.1]
  \foreach \x/\y/\z in {0/2/6,1/1/5,2/1/4,3/1/3,4/1/3,5/1/3,6/1/3,7/1/3,8/0/3}
  \foreach \t in {\y,...,\z}
  {
  \draw[very thick] (-0.8*\t,0.8*\x) rectangle (-0.8*\t +0.8,0.8*\x +0.8);
  }

\foreach \x/\y in {0/7,1/6,2/5,3/4,4/4,5/4,6/4,7/4,8/4}
  \foreach \t in {\y,...,7}
  {
  \draw[dotted] (-0.8*\t,0.8*\x) rectangle (-0.8*\t +0.8,0.8*\x +0.8);
  \draw (-0.8*\t+0.4,0.8*\x+0.4) node {\#};
  }
\draw[dotted] (-0.8,0) rectangle (0,0.8);
\draw (-0.4,0.4) node {\#};
\foreach \x in {0,...,7}
{
  \filldraw[fill = black!50!white] (0,0.8*\x) rectangle (0.8,0.8*\x+0.8);
  \draw (0.4,0.8*\x+0.4) node {W};
}
\foreach \x\y in {0/2,0/4,0/6,1/3,1/5,2/4,7/1,8/0,8/2}
  {
  \draw (-0.8*\y+0.4,0.8*\x+0.4) node {Go};
  }
  \foreach \x\y in {1/1,2/1,2/2,3/1,3/2,3/3,4/1,4/2,5/1}
  {
  \draw (-0.8*\y+0.4,0.8*\x+0.4) node {Stop};
  }
  \foreach \x\y in {0/3,0/5,1/2,1/4,2/3,8/1}
  {
  \draw (-0.8*\y+0.4,0.8*\x+0.4) node {\textcolor{gray}{Go}};
  }
  \foreach \x\y in {4/3,5/3,6/3,7/3,8/3}
  {
  \draw (-0.8*\y+0.4,0.8*\x+0.4) node {$=$};
  }
  \foreach \x\y in {5/2,6/2,6/1,7/2}
  {
  \draw (-0.8*\y+0.4,0.8*\x+0.4) node {$-$};
  }
  \draw[red,very thick] (-0.8,0.8) -- (-0.8,1.6) -- (-1.6,1.6) -- (-1.6,2.4) -- (-2.4,2.4)
		    (-2.4,3.2) -- (-1.6,3.2) -- (-1.6,4) -- (-0.8,4) -- (-0.8,4.8) -- (0,4.8)
                   (0,5.6) -- (-0.8,5.6) -- (-0.8,6.4) -- (-1.6,6.4) -- (-1.6,7.2);

 \end{tikzpicture}
  \caption{A younger sweeping counter encountering an older wall. Only the state layer of $\alph{sweeping}$ is represented,
  with greyed words for buffers.}
\label{figure:comp1}
 \end{center}
\end{figure}

\begin{figure}[!ht]
\begin{center}
 \begin{tikzpicture}
\foreach \x in {1,...,7}
{
  \filldraw[fill = black!50!white] (-1,\x-1) rectangle (0,\x);
  \draw (-0.5,\x-0.5) node {W};
}
\foreach \y/\x/\a/\b/\c in {
			    0/1/Stop/1/2, 0/2/Stop/2/1, 0/3/Stop/1/1, 0/4/Stop/1/1,
			    1/1/Stop/2/1, 1/2/Stop/0/2, 1/3/Stop/2/1, 1/4/=/1/1,
			    2/1/Stop/1/2, 2/2/Stop/2/0, 2/3/=/0/2, 2/4/=/2/1,
			    3/1/Stop/2/1, 3/2/+/0/1, 3/3/=/1/1, 3/4/=/2/0, 3/5/=/\#/1,
			    4/1/+/1/2, 4/2/+/1/1, 4/3/=/1/1, 4/4/=/0/0, 4/5/=/1/1,
			    5/2/+/1/1, 5/3/=/1/1, 5/4/=/0/0, 5/5/=/1/1,
			    6/3/=/1/1, 6/4/=/0/0, 6/5/=/1/1
			    }
{
\draw[very thick] (-\x,\y) rectangle (-\x-1,\y+1);
\draw[dotted] (-\x,\y+0.5) -- (-\x-1,\y+0.5) (-\x-0.5,\y)--(-\x-0.5,\y+0.5);
\draw (-\x-0.5,\y+0.75) node {$\a$};
\draw (-\x-0.25,\y+0.25) node {$\c$};
\draw (-\x-0.75,\y+0.25) node {$\b$};
 }
\foreach \x/\y in {0/5,1/5,2/5,3/6,4/6,5/6,6/6}
\foreach \t in {6,...,\y}
{
\draw[dotted] (-\t,\x) rectangle (-\t-1,\x+1);
\draw (-\t-0.5,\x+0.5) node {\#};
}

\draw[dotted] (-2,5) rectangle (-1,6);
\draw (-1.5,5.5) node {\#};
\draw[dotted] (-3,6) rectangle (-1,7);
\draw (-1.5,6.5) node {\#};
\draw[dotted] (-3,6) rectangle (-2,7);
\draw (-2.5,6.5) node {\#};
\draw[red,very thick] (-5,1) -- (-4,1) -- (-4,2) -- (-3,2) -- (-3,3) -- (-2,3) -- (-2,4) -- (-1,4);

\draw[very thick] (2,3) rectangle (3,4);
\draw[dotted] (2,3.5) -- (3,3.5) (2.5,3.5)--(2.5,3);
\draw (2.5,4.3) node {state};
\draw (1.9,2.7) node {time};
\draw (3.1,2.7) node {value};
 \end{tikzpicture}
\end{center}
\caption{The comparison process in detail. Here the sweeping counter is older than the wall and is destroyed. Only the layer $\alph{sweeping}$ is represented.}
\label{figure:comp2}
\end{figure}

After the comparison, two cases are possible:
\begin{itemize}
 \item if the state of the rightmost bit is $-$, the wall is destroyed and the state of the rightmost bit becomes Go. The counter then progressively resumes going forward.
 \item if the state of the rightmost bit is $+$ or $=$, it is erased. The remaining bits are progressively erased similarly to detached time counters.
\end{itemize}
Notice that if the counter is dominated, then its leftmost bit is erased at each step, preventing the comparison to start, until the counter is entirely erased.\\

Finally, the alphabet $\alph{sweeping}$ can be written as $\{\#\} \cup \{Go\}\times \{0,1,2,\#\} \cup \{Stop, +, -, 0\} \times \{0,1,2\}$.

When a sweeping counter reaches the right wall of the segment, the segment is said to be $\define{swept}$. This implies no (non-initialized) walls remain in
the segment.

\begin{fact}\label{fact:sweeptime}
 At time $k(1+\lceil\log k\rceil)$, all segments of length $k$ are swept.
\end{fact}

\begin{proof} As long as $t\leq k(1+\lceil\log k\rceil)$, any initialized sweeping counter has less than $2\lceil\log k\rceil$ cells containing a value.
The counter progresses at speed one except when it meets another wall. Each comparison takes a time equal to twice the current length of the counter.
Furthemore, two consecutive walls are separated by three cells at least (cf. Section~\ref{section:bootstrapping}).
Thus, the segment is swept in less than $k + \frac k4\cdot 2\cdot 2\lceil\log k\rceil$ steps, and we can check that $t\leq k(1+\lceil\log k\rceil)$.
\end{proof}

\begin{fact}\label{fact:attached}
 An initialized wall cannot be erased by a time counter attached to a non-initialized wall.
\end{fact}

\begin{proof} Consider two walls separated by $k\geq 3$ cells, the left being initialized and the right non-initialized. The value of the time counter attached
to the right wall cannot exceed $2^{k-3}$ at $t=1$ (since $\hspace{-0.1cm$ erases three cells to its right), it will take more than $2^k-2^{k-3}$ steps before the left wall is erased. According to Fact~\ref{fact:sweeptime}, the right wall will be destroyed in less than $k(1+\lceil\log k\rceil)$ steps, and the time counter will take at
most $k$ more steps to be erased.

For $k\geq 5$, $k(1+\log k)+k\leq 2^k - 2^{k-3}$, so the counter is erased before it reaches the left wall. For $k=4$, there cannot be another wall between them, so the destruction time is actually $\leq k + 2\log k + k \geq 2^k-2^{k-3}$. For $k=3$, the time counter of the right wall is erased at $t=1$ by the left
wall, so the right wall is immediately destroyed.
\end{proof}

\subsection{Computation and copy}

\subsubsection{Computation}\label{section:computation}
Computation takes place in the area delimited by the time counter attached to the right wall. $\alph{comp}$ is divided into three layers, on which three Turing machines
$\mathcal{TM}_i=(Q_i,\Gamma_i,\#,q_{0_i},\delta_i,Q_{F_i})$ are simulated. We use the alphabet
$\alph{comp} = \bigotimes_{i=1}^3 \Gamma_i\times(Q_i\cup\#)$. For $i=1,2,3$, $comp_i$ is the projection on the corresponding layer, and we identify
$((\#,\#),(\#,\#),(\#,\#))$ with $\#$.\\

On each layer, the left part contains the content of the tape, and the right part contains the state of the machine in exactly one cell (to represent the head), and $\#$ everywhere else. If a cell is outside a time counter, the computation layer is deleted. The evolution of the tapes is governed by the rules of the machine, i.e.:
\begin{itemize}
 \item if $time(u_0) = \#$ then $comp_i(F(u)_0) = \#$;
 \item if the head is on $u_0$ and $\delta(comp_i(u)) = (q,\gamma,\cdot )$, then $comp_i(F(u)_0) = (q,\gamma)$;
 \item if the head is on $u_1$, $\delta(comp_i(u_1)) = (q,\gamma,\leftarrow)$ and $u_0 = (\#,\gamma')$,
 then $comp_i(F(u)_1) = (\#,\gamma)$ and $comp_i(F(u)_0) = (q,\gamma')$;
 \item similarly if the head is on $u_{-1}$ and $\delta(comp_i(u_{-1})) = (q,\gamma,\rightarrow)$;
 \item otherwise, $comp_i(F(u)_0) = comp_i(u_0)$.
\end{itemize}

We now describe the operations expected to be performed during the time interval $[T_{n-1}, T_{n}]$. Sometimes a machine can read its input or write its output on another layer. Suppose that layer 1 receives $n$ as input. The machines:
\begin{itemize}
 \item replace $n$ by $n+1$ on layer 1;
 \item compute $w_n$ on layer 2, outputting it on the output layer;
 \item compute $T_{n}$ on layer 3;
 \item when $t = T_{n}$ ($t$ being written on the time layer), it initializes the next computation and the copy, or the merging with its right segment.
\end{itemize}

Copy and merging are detailed in next subsections. \\

All these operations must be performed in less than $T_{n} - T_{n-1}$ steps, and the machine can only use the space used by the time counter.

First we suppose that each $w_n$ can be computed in space $\sqrt{n}$, defining if necessary a new sequence where each $w_n$ is repeated as long as there is not enough space to compute $w_{n+1}$. Now fix $T_{n} - T_{n-1} = q^{\lfloor \sqrt n\rfloor}$, where $q$ is such that $\textrm{Card}(\Gamma_2)^{\sqrt{n}}\times\sqrt{n}\times\textrm{Card}(Q_2)$ where $\Gamma_2$ and $Q_2$ correspond to the Turing machine of layer~2. In this way, between $T_{n-1}$ and $T_{n}$ the Turing machine of layer~2 has necessarily enough time to compute $w_n$ in space $\sqrt{n}$.

Moreover, at time $T_{n-1}$ the time counter is longer than $\log_3(T_{n-1})\geq \log_3(q^{\sqrt{n-1}})$ (the counter uses three letters) and this longer than $\sqrt{n}$ for $q\geq 5$. For layers 1 and 3, the time and space bounds are verified asymptotically, i.e. there exists machines satisfying these bounds for $n>N$. Let $t_N$ be the maximal time necessary
for those machines to perform those operations when $n<N$; we can fix $T_{n+1} - T_n = t_N$ when $n<N$, which has no influence on the asymptotic behavior of $T_n$ and ensures that the machines satisfies the time bound for any $n$. For the space bound, it is always possible to compress the space by a constant factor
(by grouping tape cells) so that the space bound is satisfied for $n<N$, with no impact on the computing.

\subsubsection{Copying}\label{section:copy}
At time $T_{n+1}\ (n\geq 0)$, $w_n$ has been output on the output layer.
If the segment is not merging with its right segment, the Turing machine triggers the copying process by copying the first letter of $w_n$ from the output
layer to the copy layer.

\begin{description}
 \item[First phase] Inside the time counter, the word on the copy layer progresses at speed -2, and a letter at each step is copied from the output
layer to the tail of the word;
 \item[Second phase] When the head is out of the time counter, the word keeps progressing at speed -2 but the head loses one letter at each step and
copies it on the output layer. The tail keeps copying letters from the output layer.
\end{description}

Intuitively, the cellular automaton performs a catterpillar-like movement between the copy and output layers (see Figure~\ref{figure:copy} for an example). The process ends when it meets a wall or a sweeping counter
to its left. Thus, $\alph{copy} = \B\cup\{\#\}$.

\begin{figure}[!ht]
\begin{center}
 \begin{tikzpicture}
\foreach \x in {1,...,7}
{
  \filldraw[fill = black!50!white] (0,\x) rectangle (0.8,\x+0.8);
  \draw (0.4,\x+0.4) node {W};
}
\foreach \x in {1,...,7}
{
 \foreach \y in {0,...,3}
  {
   \draw (-0.8*\y,\x) rectangle (-0.8*\y-0.8,\x+0.4);
  }

    \draw (-0.4,\x+0.2) node {$1$};
    \draw (-1.2,\x+0.2) node {$0$};
    \draw (-2,\x+0.2) node {$1$};
    \draw (-2.8,\x+0.2) node {$1$};
}
\foreach \x/\y in {1/1,2/3,3/3,3/5,4/5,4/4,3.6/6,4.6/6,5/6,5/7,6/7,6/8,5.6/6,5.6/8,6.6/6,6.6/8,6.6/9,7/9}
{
   \draw (-0.8*\y,\x+0.4) rectangle (-0.8*\y+0.8,\x+0.8);
   \draw (-0.8*\y+0.4,\x+0.6) node {$1$};
}
\foreach \x/\y in {2/2,3/4,4/6,4.6/7,5.6/7,6.6/7,7/8}
{
   \draw (-0.8*\y,\x+0.4) rectangle (-0.8*\y+0.8,\x+0.8);
   \draw (-0.8*\y+0.4,\x+0.6) node {$0$};
}
\draw[red,very thick] (-4,0.8) -- (-4,8);
\foreach \x/\y in {1/4,1.4/1,1.4/2,1.4/3,1.4/4,1.4/5,1.4/6,1.4/7,1.4/8,2/4,2.4/0,2.4/3,2.4/4,2.4/5,2.4/6,2.4/7,2.4/8,3/4,3.4/0,3.4/1,3.4/5,3.4/6,3.4/7,3.4/8,
   4/4,4.4/0,4.4/1,4.4/2,4.4/6,4.4/7,4.4/8,5/4,5.4/0,5.4/1,5.4/2,5.4/3,5.4/4,5.4/7,5.4/8,6/4,6.4/0,6.4/1,6.4/2,6.4/3,6.4/4,6.4/5,6.4/8,7/4,7.4/0,7.4/1,7.4/2,
   7.4/3,7.4/4,7.4/5,7.4/6}
{
   \draw[dotted] (-0.8*\y,\x) rectangle (-0.8*\y-0.8,\x+0.4);
   \draw (-0.8*\y-0.4,\x+0.2) node {\#};
}
\foreach \x/\y in {1/5,1/6,1/7,1/8,2/5,2/6,2/7,2/8,3/5,3/6,3/7,3/8,4/6,4/7,4/8,5/7,5/8,6/8}
{
   \draw[dotted] (-0.8*\y,\x) rectangle (-0.8*\y-0.8,\x+0.4);
   \draw (-0.8*\y-0.4,\x+0.2) node {?};
}
\draw (2.1,3.4) rectangle (2.9,3.8) rectangle (2.1,4.2);
\draw (3.5,3.6) node {\small{output}} ;
\draw (3.5,4) node {\small{copy}} ;

\draw[->] (-8,0.5) -- (-8,8);
\draw (-8.2,8.4) node {time};
\draw (-8.1,1) -- (-7.9,1);
\draw (-8.4,1) node {$T_n$};
\end{tikzpicture}
\end{center}
\caption{Beginning of the copying process, with $w_n = 1101$. Only the layers $\alph{copy}$ and $\alph{output}$ are represented. The thick line is the limit of the time counter.}
\label{figure:copy}
\end{figure}

\subsection{Merging of segments}\label{section:merge}

At time $T_n$, all segments of length $n$ merge with their left neighbor, so that the density of walls will tend to 0.\\

To do so, at time $T_{n-1}$ is initialized a \define{merging counter} of value $2n$ on the merge layer, decrementing at each step. Since
the value of $n$ is written on one computing layer, it is copied (with an additional 0) on the merge layer using an auxiliary state
$\hspace{-0.1cm$ (\define{copy}). This counter is similar to incrementing counters, except it uses -1 as negative carry.\\

Simultaneously, a signal is sent to the right and bounces off the right wall. Thus, the segment is of length $n$ iff the signal returns before
the end of the decrementation.

In this case, a symbol $\hspace{-0.1cm$ (\define{merge}) is created on the merge layer, to indicate the wall will be destroyed at next $T_n$;
otherwise, the output will be copied in the output layer as described above. Thus $\alph{merge}
=\{-1,0,1,\hspace{-0.1cm,\hspace{-0.1cm\}\times\{\rightarrow,\leftarrow\}\cup\{\#\}$, see Figure~\ref{figure:merge} for an example of this process.\\

 \begin{figure}[!ht]
\begin{center}
\begin{tikzpicture}
\draw (-4.4,-0.4) -- (-4.4,5.6);
\draw[dotted] (-4.4,5.6) -- (-4.4,6.4);
\draw[->] (-4.4,6.4) -- (-4.4,8);
\draw (-4.7,8.2) node {time};
\draw (-4.5,0) -- (-4.3,0);
\draw (-4.75,0) node {$T_2$};
\draw (-4.5,7.2) -- (-4.3,7.2);
\draw (-4.75,7.2) node {$T_3$};
\foreach \x in {0,...,6,8}
{
  \filldraw[fill = black!50!white] (0,0.8*\x) rectangle (0.8,0.8*\x+0.8) (3.2,0.8*\x) rectangle (4,0.8*\x+0.8);
  \draw (0.4,0.8*\x+0.4) node {W};
  \draw (3.6,0.8*\x+0.4) node {W};
}
  \filldraw[fill = black!50!white] (3.2,7.2) rectangle (4,8);
  \draw (3.6,7.6) node {W};

\foreach \x\y in {0/1,1/2,2/3}
 {
   \draw[very thick] (\y*0.8,\x*0.8) rectangle (\y*0.8+0.8,\x*0.8+0.8);
   \draw (\y*0.8+0.4,\x*0.8+0.4) node {$\rightarrow$};
   \draw[very thick] (\y*0.8,4-\x*0.8) rectangle (\y*0.8+0.8,4.8-\x*0.8);
   \draw (\y*0.8+0.4,4-\x*0.8+0.4) node {$\leftarrow$};
 }

\foreach \x\y in {0/2,0/3,0/-3,0/-4,0/-5,1/1,1/3,1/-4,1/-5,2/1,2/2,2/-4,2/-5,3/1,3/2,3/-4,3/-5,4/1,4/3,4/-4,4/-5,5/2,5/3,5/-3,5/-4,5/-5,
6/1,6/2,6/3,6/-2,6/-3,6/-4,6/-5,8/-2,8/-3,8/-4,8/-5,8/1,8/2,8/3,9/0,9/-1,9/-2,9/-3,9/-4,9/-5,9/1,9/2,9/3}
{
  \draw[dotted] (\y*0.8,\x*0.8) rectangle (\y*0.8+0.8,\x*0.8+0.8);
  \draw (\y*0.8+0.4,\x*0.8+0.4) node {\#};
}

\foreach \x\y in {0/2,1/3}
{
   \draw[very thick] (-\y*0.8,\x*0.8) rectangle (-\y*0.8+0.8,\x*0.8+0.8);
   \draw (-\y*0.8+0.4,\x*0.8+0.4) node {C};
}
\foreach \x\y in {1/2,2/3,3/3,4/3,5/2}
{
   \draw[very thick] (-\y*0.8,\x*0.8) rectangle (-\y*0.8+0.8,\x*0.8+0.8);
   \draw (-\y*0.8+0.4,\x*0.8+0.4) node {$1$};
}
\foreach \x\y in {0/1,2/1,2/2,3/2,4/1}
{
   \draw[very thick] (-\y*0.8,\x*0.8) rectangle (-\y*0.8+0.8,\x*0.8+0.8);
   \draw (-\y*0.8+0.4,\x*0.8+0.4) node {$0$};
}
\foreach \x\y in {1/1,3/1,4/2,5/1}
{
   \draw[very thick] (-\y*0.8,\x*0.8) rectangle (-\y*0.8+0.8,\x*0.8+0.8);
   \draw (-\y*0.8+0.4,\x*0.8+0.4) node {$-1$};
}
\draw[very thick] (-0.8,4.8) rectangle (0,5.6);
\draw (-0.4,5.2) node {$M$};
\draw[very thick] (-0.8,6.4) rectangle (0,7.2);
\draw (-0.4,6.8) node {$M$};
\draw[dotted] (-0.4,5.8) -- (-0.4,6.2) (0.4,5.8) -- (0.4,6.2) (3.6,5.8) -- (3.6,6.2);
\end{tikzpicture}
\end{center}
\caption{Determination of the length of the segment. Here the right segment is of length $3$ and the wall merges at time $T_3$.
The counter of the right segment has been omitted for clarity.}
\label{figure:merge}
\end{figure}

\begin{fact}
 All left walls of segments of length $k$ are erased simultaneously at time $\min (T_k, 2^k+k)$.
\end{fact}

\begin{proof} Except for the situation described above, the only other way for an initialized wall to be erased is a time counter attached to an initialized
wall, see Facts~\ref{fact:detached} and \ref{fact:attached}.
A redundant binary counter whose initial value is 0 reaches length $k$ at time $2^k+k$.\\
\end{proof}

We will consider from now on that $n$ is large enough so that $2^n+n > T_n$.

\begin{definition}
Denote
\begin{align*}
&\Gamma^t_{l,k} =\left\{x\in\az: [0,l]\text{ is included in a segment of }F^t(x)\text{ of length }k\right\} \\
&\Gamma^t_{l,\geq k}=\bigcup_{i\geq k} \Gamma^t_{l,i} \quad \text{and}\quad \Gamma^t_l=\Gamma^t_{l,\geq 1}
\end{align*}
\end{definition}

\begin{proposition}\label{prop:LargerSegment}
Let $\mu\in\Mergfull(\az)$. For all
$l,k\in\N$, one has $\mu(\Gamma^t_{l,\geq k})\underset{t\to\infty}{\longrightarrow} 0.$
\end{proposition}
\begin{proof}
When $t\geq T_n$, no configuration can contain a segment smaller than $n$. Moreover, by $\s$-ergodicity, since $\mu\left(\left[{\hspace{-0.1cm}\right]\bigcap_{i\in [1,n]}\s^i\left(\overline{\left[{\hspace{-0.1cm}\right]}\right)\right)\neq0$, there exists $\mu$-almost surely segments of length larger that $n$ at $t=0$  and those segments survive up to time $T_n$. \\

Therefore, the cell 0 is $\mu$-almost surely included in a segment at time $T_n$. Since this segment is longer than $n$ and by $\s$-invariance, the probability that $[0,l]$ crosses a border of the segment tends to 0 as $n$ tends to infinity.
\end{proof}

\subsection{Correctness of the cellular automaton}
\subsubsection{Acceptable segments}

\begin{proposition}\label{Equiv-tn}
 $T_n = \Theta(\lfloor\sqrt n\rfloor q^{\lfloor\sqrt n\rfloor})$ where $q$ is defined in Section~\ref{section:computation}.
\end{proposition}

\begin{proof}
$T_n = \sum_{k=1}^n T_k-T_{k-1}$. Since asymptotically $T_{k+1} - T_k = q^{\lfloor\sqrt k\rfloor}$, and:
\[(2\lfloor\sqrt{n}\rfloor-1)q^{\lfloor\sqrt{n}\rfloor-1}\leq \sum_{k=1}^{\lfloor\sqrt n\rfloor-1} (2k+1)q^k \leq
\sum_{k=1}^n q^{\lfloor\sqrt k\rfloor}\leq \sum_{k=1}^{\lfloor\sqrt n\rfloor} (2k+1)q^k
\leq (2\lfloor\sqrt n\rfloor+1)q^{\lfloor\sqrt n\rfloor+1}.\] the proposition follows.
\end{proof}

In Proposition~\ref{prop:LargerSegment}, we did not control the length of the segment at time $t$. In order to approximate a measure, we want to ensure the copy
is finished before the time $T_{n+1}$, which requires that the segment is not too large.

\begin{definition}\label{def:AcceptableSegment}
Let $x\in\az$, $[i,j]$ a segment at time $t\in[T_n,T_{n+1}]$. It is \define{acceptable} if $j-i-1\leq K_n = \sqrt{T_{n+1}-T_n}$. For $n$ large enough $K_n=q^{\frac{\lfloor\sqrt n\rfloor}{2}}$.
\end{definition}

\begin{proposition}\label{prop:AcceptableIsSwept}
 For $t$ large enough, an acceptable segment is swept.
\end{proposition}

\begin{proof}
When $T_n\leq t<T_{n+1}$, for an acceptable segment of length $k$, we have $k(1+\log k) \leq K_n(1+\log(K_n)) = o(T_n)$
by Proposition~\ref{Equiv-tn}. Taking $n$ large enough, we conclude by Fact~\ref{fact:sweeptime}.
\end{proof}

\begin{proposition}\label{prop:AllAcceptable}
Let $\mu\in\Mmixfull(\az)$. One has $\mu(\Gamma^{T_n}_{l,\geq K_n})\underset{n\to\infty}{\longrightarrow} 0$, that is to say:
\[\mu(\{x\in\A^\Z : [0,l]\textrm{ is in an acceptable segment of }F^t(x)\})\underset{t\to\infty}{\longrightarrow} 1\]
and the rate of convergence is exponential.
\end{proposition}
\begin{proof}

Any segment at time $T_n$ corresponds, at time $T_{n-1}$, to a segment of arbitrary size plus an arbitrary number of segments of size $n$. For $l\leq n$,
define \[\Delta^t_{j,n,\alpha}=\{x\in\az: \textnormal{starting from $j$ there is a strip of $\alpha$ consecutive segments of size $n$ in } F^t(x)\}.\]
Take any $L>2n$, and depending on whether there are more or less than $\left\lfloor \frac Ln\right\rfloor$ such segments of size $n$ at time $T_{n-1}$ (see Figure~\ref{prop:AllAcceptable} for an illustration of this decomposition), one has:

\begin{align}\label{acc1}
\Gamma^{T_n}_{l,\geq k} &\subset \bigcup_{i=-L+l}^0\s^i\left(\Gamma^{T_{n-1}}_{l,\geq k-L}\right) \cup \bigcup_{j=0}^{k-1}
\Delta^{T_{n-1}}_{j,n,\left\lfloor \frac Ln\right\rfloor}\notag\\
\mu\left(\Gamma^{T_n}_{l,\geq k}\right) &\leq L\mu\left(\Gamma^{T_{n-1}}_{l,\geq k-L}\right)+ k\mu\left(\Delta^{T_{n-1}}_{0,n,\left\lfloor \frac
Ln\right\rfloor}\right)
\end{align}

Thus we try to bound the value of $\mu(\Delta^t_{0,n,\alpha})$. If $x\in\Delta^t_{0,n,\alpha}$ then for all $i\in[0,\alpha]$ one has
$x_{in}={\hspace{-0.1cm}$ (corresponding to initialized walls at time $t$). For any $m>0$, by considering one symbol out of $m$:
\begin{align}
\mu\left(\Delta^t_{0,n,\alpha}\right)&\leq \mu\left(\bigcap_{i\in[0,\alpha]}\s^{in}\left(\left[{\hspace{-0.1cm}\right]\right)
\right)\notag\\
&\leq \mu\left(\bigcap_{i\in\left[0,\lfloor\frac \alpha m\rfloor\right]}\s^{in\cdot m}\left(\left[{\hspace{-0.1cm}\right]\right) \right)\notag\\
&\leq (1+\psi_\mu(mn))^{\lfloor\frac \alpha m\rfloor}\mu\left(\left[{\hspace{-0.1cm}\right]\right)^{\lfloor\frac \alpha m\rfloor+1}.\label{acc2}
\end{align}

\begin{figure}[!ht]
 \begin{center}
  \begin{tikzpicture}
   \draw (0,0) -- (0,3) (13,0) -- (13,3);
   \foreach \x in {4,...,12}
   {
   \draw (\x,0) -- (\x,1.5);

   \draw (\x-.25,0) rectangle (\x,0.25);
   \draw (\x-.125,0.1) node {\tiny M};
   \draw[->, dotted] (\x-.125,0.3) -- (\x-.125,1.2);
   \draw (\x-.25,1.25) rectangle (\x,1.5);
   \draw (\x-.125,1.35) node {\tiny M};
   }
   \foreach \x in {4,7,10,13}
   {
   \draw[very thick] (\x,0) -- (\x,1.5);
   }
   \draw [<->] (4,-0.3) -- (13,-0.3);
   \draw (8.5,-0.6) node {strip};
   \draw [<->] (4.05,0.5) -- (4.95,0.5);
   \draw [<->] (4,1.7) -- (7,1.7);
   \draw (5.5,1.9) node {$m\cdot n$};
   \draw (4.5,0.3) node {$n$};
   \draw[dotted] (-0.6,1.5) -- (13.5,1.5);
   \draw[->] (-0.4,-0.3) -- (-0.4,3.3);
   \draw (-0.7,3.6) node {time};
   \draw (-1,1.5) node {$T_n$};
   \draw[dotted] (7.5,0) -- (7.5,3);
   \draw (7.5,3.5) node {0};
   \draw[dotted] (4,0) -- (4,3);
   \draw (4,3.5) node {j};

  \end{tikzpicture}
  \caption{Illustration of the proof of Proposition~\ref{prop:AllAcceptable} with $\alpha=9$ and $m=3$.}\label{figure:AllAcceptable}
 \end{center}
\end{figure}

Now take any $M>n$. Using (\ref{acc2}) with $m = \left\lceil \frac Mn\right\rceil$ inside equation (\ref{acc1}):
\begin{align*}
\mu\left(\Gamma^{T_n}_{l,\geq k}\right)& \leq L\mu\left(\Gamma^{T_{n-1}}_{l,\geq k-L}\right)+ k\left[1+\psi_\mu\left(n\cdot \left\lceil \frac
Mn\right\rceil\right)\right]^{\frac {L}{M}}\mu\left(\left[{\hspace{-0.1cm}\right]\right)^{\frac{L}{M}+1}\\
& \leq L\mu\left(\Gamma^{T_{n-1}}_{l,\geq k-L}\right)+ k\left[(1+\psi_\mu(M))\mu\left(\left[{\hspace{-0.1cm}\right]\right)\right]^{\frac{L}{M}}\\
\end{align*}

Now, if $k\geq nL$, we obtain by induction:
\begin{align}\label{acc3}
\mu\left(\Gamma^{T_n}_{l,\geq k}\right) &\leq L^{n}\mu\left(\Gamma^{0}_{l,\geq
k-nL}\right)+kL^{n}\left[(1+\psi_\mu(M))\mu\left(\left[{\hspace{-0.1cm}\right]\right)\right]^{\frac{L}{M}}
\end{align}

For the left-hand term, we have:
\begin{align*}
\mu\left(\Gamma^{0}_{l,\geq k-nL}(x)\right)&\leq
\mu\left(\bigcup_{j\in[-k+nL,-1]}\bigcap_{i\in[0,k-nL]}\s^{j+i}\left(\overline{\left[{\hspace{-0.1cm}\right]}\right)\right) \\
&\leq \mu\left(\bigcup_{j\in[-k+nL,-1]}\bigcap_{i\in[0,\lfloor\frac{k-nL}{n}\rfloor]}\s^{j+in}\left(\overline{\left[{\hspace{-0.1cm}\right]}\right)\right) \\
&\leq (k-nL)(1+\psi_\mu(n))^{\lfloor\frac{k-nL}{n}\rfloor} \mu\left(\overline{\left[{\hspace{-0.1cm}\right]}\right)^{\lfloor\frac{k-nL}{n}\rfloor+1}
\end{align*}
the second line being obtained by considering one symbol out of every $n$. Putting $M = n$, $L = n^2\sqrt n$, and $k = K_n$ in (\ref{acc3}) then since
$\psi_\mu(n) \to 0$, we have $\mu(\Gamma^{T_n}_{\geq K_n})\underset{n\to\infty}{\longrightarrow}0$ and the rate of
convergence is exponential.
\end{proof}

\begin{remark}\label{rem:polynom}
 Remark that it is possible to take any value for $K_n$ as soon as $K_n = \omega(n^2\sqrt{n})$.
\end{remark}

\subsubsection{Density of auxiliary states}\label{section:auxiliary}

\begin{proposition}\label{prop:copy}
Let $\mu\in\Mergfull(\az)$ and $u\in\B^l$ for some fixed $l$. For a given segment length $k$ such that $n+1\leq k\leq K_n$ one has:
\begin{itemize}
\item If $t\in[T_n+k,T_{n+1}]$, \[\left|\mu\left(F^{-t}([u])|\Gamma^{T_n}_{l,k}\right)-\meas{w_{n}}([u])\right| = O\left(\frac 1{\sqrt{n}}\right);\]
\item If $t\in[T_n,T_n+k]$ one has
\[\left|\mu\left(F^{-t}([u])|\Gamma^{T_n}_{l,k}\right)-\left(\frac{k-(t-T_n)}{k}\meas{w_{n-1}}([u])+\frac{t-T_n}{k}\meas{w_{n}}([u])\right)\right| = O\left(\frac 1{\sqrt{n}}\right).\]
\end{itemize}
\end{proposition}

\begin{figure}[!ht]
\begin{center}
 \begin{tikzpicture}
 \fill[black!20] (0.6,0) -- (8.4,0) -- (8.4,0.6) -- (3.6,5.4) -- (0.6,5.4) -- cycle;
 \draw[red, very thick] (8.4,0.6) -- (3.6,5.4);
 \draw (2.8,1.8) node {$w_{n-1}$};
 \draw (5.7,4.5) node {$w_n$};
 \foreach \x in {0,14}
 {
 \foreach \y in {0,...,8}
 {
 \filldraw[fill = black!50!] (0.6*\x,0.6*\y) rectangle (0.6*\x+.6,0.6*\y+.6);
 \draw (0.6*\x+0.3,0.6*\y+0.3) node {W};
 }
 }
 \filldraw[fill = black!50!] (0.6*8,0) rectangle (0.6*8+.6,.6);
 \draw (0.6*8+0.3,0.3) node {W};
 \fill[pattern = north east lines] (0.6*8,0.6) -- (0.6*8+.6,0.6) -- (0.6*8+.6,3.6) -- (0.6*8,4.2) -- cycle;
 \filldraw[fill = black!50!] (0.6*11,0) rectangle (0.6*11+.6,.6);
 \draw (0.6*11+0.3,0.3) node {W};
 \fill[pattern = north east lines] (0.6*11,0.6) -- (0.6*11+.6,0.6) -- (0.6*11+.6,1.8) -- (0.6*11,2.4) -- cycle;
 \end{tikzpicture}
\caption{Illustration of Proposition~\ref{prop:copy}. The output is not correctly written in dashed areas because of the destruction of a wall.}
\end{center}
\end{figure}

\begin{proof}

We write $\Gamma^{T_n}_{[i,i+k]} = \left\{x\in\az\ |\ [i,i+k]\textrm{ is a segment at time }T_n\right\}$, so that
\[\Gamma^{T_n}_{l,k} = \bigsqcup_{i=-k+l}^{-1}\Gamma^{T_n}_{[i,i+k+1]} = \bigsqcup_{i=-k+l}^{-1}\s^i(\Gamma^{T_n}_{[-1,k]})\quad\quad\tx{(disjoint union)}.\]
Suppose $x\in\Gamma^{T_n}_{[-1,k]}$. Since such a segment is acceptable, it is swept, and any non-initialized counter or wall has been destroyed. Since $|w_n| \leq\sqrt n$ (smaller than the computing space), the copying process will use less than $\sqrt n$ auxiliary cells.

\paragraph{First point:} The copying process progresses at speed one, so at time $T_n+k$ the copy of the word is finished (since $T_n+k\leq T_{n+1}$), and the
segment is constituted
only by copies of $w_n$ except for the time counter and computation area ($O(\sqrt n)$ cells) and a merging signal (one cell).\\

Therefore for all $x\in\Gamma^{T_n}_{[-1,k]}$, one has $\left|\frac {\textrm{Card}\left(\{i\in [0,k-1] : F^t(x)\in[u]_i\}\right)}k - \meas{w_n}([u])\right| = \frac {O(\sqrt n)}k = O\left(\frac 1{\sqrt{n}}\right)$, taking into
account the time counter, the merging signal,
and the last copy of $w_n$ in the segment which can be incomplete, and since $k\geq n$. Thus we have
\[\left|\frac 1k\sum_{i=0}^{k-1}\mu\left(F^{-t}([u]_i)\ |\ \Gamma^{T_n}_{[-1,k]}\right)- \meas{w_n}([u])\right| = O\left(\frac 1{\sqrt n}\right).\]

Since $\mu$ is $\s$-invariant, $\mu\left(F^{-t}([u]_i)\ |\ \Gamma^{T_n}_{[-1,k]}\right) = \mu\left(F^{-t}([u]_0)\ |\ \Gamma^{T_n}_{[i,i+k+1]}\right)$. So:
\begin{align*}\mu\left(F^{-t}([u]_0)\ |\ \Gamma^{T_n}_{l,k}\right) =& \sum_{i=-k+l}^{-1} \mu\left(F^{-t}([u]_0)\ |\ \Gamma^{T_n}_{[i,i+k+1]}\right)\cdot
\mu\left(\Gamma^{T_n}_{[i,i+k+1]}\ |\ \Gamma^{T_n}_{l,k}\right)\\ =& \frac{1}{k-l} \sum_{i=-k+l}^{-1} \mu\left(F^{-t}([u]_0)\ |\ \Gamma^{T_n}_{[i,i+k+1]}\right)
\end{align*}
 by $\s$-invariance and disjoint union of $\Gamma^{T_n}_{l,k}$. The result follows.

\paragraph{Second point:} When $t\in[T_n,T_n+k]$, the copy is still taking place, with $t-T_n$ cells containing copies of $w_n$ and the rest containing copies
of $w_{n-1}$, except for: the computation part, the copy auxiliary states, the merging signal, and possibly defects when a wall has been destroyed at time $T_n$
(there are at most $\frac kn$ of them). Therefore \[\left|\frac {\#\{i\in [0,k-1]: F^t(x)\in[u]_i\}}k -\left(\frac{k-(t-T_n)}{k}\meas{w_{n-1}}([u])+\frac{t-T_n}{k}
\meas{w_{n}}([u])\right)\right| = \frac 1k O(\sqrt n)\cdot \frac kn \]
$\frac 1k O(\sqrt n)\cdot \frac kn = O\left(\frac 1{\sqrt{n}}\right)$ since $k\geq n$. Using the same reasoning as the first point, we conclude.

\end{proof}

\subsubsection{Proof of Theorem~\ref{MainTheorem} - first point}\label{section:FirstPoint}

Let $\mu\in\Mmixfull(\az)$ and $u\in\B^{l+1}$. Since at time $T_n$ there are no segment of length less that $n$, and by Propositions~\ref{prop:LargerSegment} and \ref{prop:AllAcceptable}, one has
$\max\left\{\mu\left(\bigcup_{n\leq k\leq K_n}\Gamma^t_{l,k}\right):T_n\leq t<T_{n+1}\right\}\underset{n\to\infty}{\longrightarrow} 1$ exponentially fast. Therefore:
\[\max_{T_n\leq t<T_{n+1}}F^t_{\ast}\mu([u]) - \sum_{k=n}^{K_n}\mu\left(F^{-t}([u])|\Gamma^t_{l,k}\right)\mu\left(\Gamma^t_{l,k}\right) = O\left(\frac{1}{\sqrt{n}}\right).\]

and $\Gamma^t_{l,k} = \Gamma^{T_n}_{l,k}$ since no segment is destroyed between $T_n$ and $T_{n+1}$. By Proposition~\ref{prop:copy},
\begin{align*}
\max_{T_n\leq t<T_{n+1}}\left|\F^t\mu([u])-\sum_{k=n}^{K_n}\mu(\Gamma^{T_n}_{l,k})\left(\max\left(0,\frac{k-(t-T_n)}{k}\right)\right.\right.&\meas{w_{n}}([u])\\
+\min\left(1,\frac{t-T_n}k\right)&\left.\left.\meas{w_{n-1}}([u])\right)\right| = O\left(\frac 1{\sqrt n}\right)
\end{align*}

\[\max_{T_n\leq t<T_{n+1}}\left|\F^t\mu([u])-\left(f_n(t)\meas{w_{n}}([u])+(1-f_n(t))\meas{w_{n-1}}([u])\right)\right| = O\left(\frac 1{\sqrt n}\right).\]

where $f_n$ is the piecewise affine function defined by \[\begin{array}{lccl}f_n:&[T_n,T_{n+1}]&\longrightarrow&[0,1]\\
&t&\longmapsto& \sum_{k=n}^{K_n}\max\left(0,\frac{k-(t-T_n)}k\right)\mu\left(\Gamma^{T_n}_{l,k}\right)
+ \frac{t-T_n}{T_{n+1}-T_n}\mu\left(\Gamma^{T_n}_{l,>K_n}\right).\end{array}\]
The second term is chosen so that $f_n(T_n) = 0$ and $f_n(T_{n+1}) = 1$, but it converges to 0 exponentially and thus does not affect the equation.
Therefore \[\max_{T_n\leq t<T_{n+1}}\dm\left(F^t_{\ast}\mu,\left[\meas{w_n},\meas{w_{n+1}}\right]\right) = O\left(\frac 1{\sqrt n}\right).\]

Since $f_n$ is $\frac{1}{n}$ Lipschitz on $[T_n,T_{n+1}]$, we deduce that
\[\max_{\nu\in\left[\meas{w_n},\meas{w_{n+1}}\right]}\dm\left(\nu,\left\{F^{t}_{\ast}\mu\ |\ T_n\leq t<T_{n+1}\right\}\right)= O\left(\frac 1{\sqrt n}\right).\]

We conclude that $\add(F,\mu)=\add((w_n)_{n\in\N})$. \\

When $w_n$ is computable in space $\sqrt{n}$, by Proposition~\ref{Equiv-tn} we find that the rate of convergence is
 \[\dm\left(\F^t\mu,\add\left((w_n)_{n\in\N}\right)\right)\leq O\left(\frac{1}{\log(t)}\right)+\sup\left\{\dm\left(\nu,\add\left((w_n)_{n\in\N}\right)\right):\nu\in\bigcup_{n\geq n(t)}\left[\meas{w_n},\meas{w_{n+1}}\right]\right\},\]
where $n(t)=\Theta(\log(t)^2)$. We recall that $w_n$ can always be computed in space $\sqrt{n}$ by repeating elements.

\subsubsection{Proof of Theorem~\ref{MainTheorem} - second point}\label{section:SecondPoint}

Assume that $\add((w_i)_{i\in\N})=\{\nu\}$, and let $F$ be the cellular automaton associated with this sequence described above. Consider $\mu\in\Mergfull(\az)$ and $u\in\B^{l+1}$.
Since $\mu$ is not assumed to be $\psi$-mixing, Proposition~\ref{prop:AllAcceptable} does not apply, and there is no guarantee most segments are acceptable.
However, since $\mu$ is ergodic, so is $\F^t\mu$ for all $t$, and $\mu(\Gamma^t_{l,\geq k}) \underset{k\to\infty}{\longrightarrow} 0$.

\Claim{$\mu(F^t(x)_0 \in \A\backslash \B) \underset{t\to\infty}{\longrightarrow} 0$, i.e., the density of auxiliary states tends to 0.}
\bclaimprf Suppose we are in an initial segment of length $k$.
Detached time counters, Turing machines and merging counters initially present are destroyed in less than $k$ steps.
Similarly, left merging signals and copy auxiliary states initially present progress at speed -1, so they are destroyed before time $k$.
An uninitialized wall is destroyed after $k(1+\log k)$ steps at most, and any counter attached to it are destroyed after
less than $k$ more steps. For all those states, the probability of apparition after time $t = k(2+\log k)$ is less than
$\mu(\Gamma_{\geq k}^0)\underset{k\to\infty}\longrightarrow 0$.

At time $T_n$, all segments are longer than $n$, so the density of walls is less than $\frac 1n$. Furthermore, the density of auxiliary states that have been generated by an initialized wall
inside each segment is $O\left(\frac 1{\sqrt n}\right)$.

Only uninitialized sweeping counters and right merging signals remain. Inside each segment, call \define{non-swept area} the interval between the initialized
sweeping counter of the left wall and the rightmost cell containing one of those two states. At each step, this area loses one cell to
its right but may grow by one cell to its left. Notice that merging with other segments cannot increase this area since segments of length $n$ at time
$T_n$ are swept (see Figure~\ref{figure:sweepVsNonSweep}).

\begin{figure}[!ht]
 \begin{center}
  \begin{tikzpicture}
   \fill[black!10!white] (1,0) -- (4,3) -- (7.9,3) -- (5.9,1) -- (5.9,0) -- cycle;
   \fill[black!10!white] (5.9,0) -- (6.6,0.7) -- (6.6,0) -- cycle;
   \fill[black!10!white] (6.6,0) -- (7.3,0.7) -- (7.3,0) -- cycle;
   \fill[black!10!white] (7.3,0) -- (8,0.7) -- (8,0) -- cycle;
   \fill[black!10!white] (8,0) -- (9,1) -- (9,0) -- cycle;
   \fill[black!10!white] (9,0) -- (10,1) -- (10,0) -- cycle;
   \draw (1,0) -- (1,3);
   \draw[very thick] (1,0) -- (4,3);
   \draw (5.9,0) -- (5.9,1);
   \draw[very thick] (5.9,0) -- (6.6,0.7);
   \draw (6.6,0) -- (6.6,1);
   \draw[very thick] (6.6,0) -- (7.3,0.7);
   \draw (7.3,0) -- (7.3,1);
   \draw[very thick] (7.3,0) -- (8,0.7);
   \draw (8,0) -- (8,2);
   \draw[very thick] (8,0) -- (9,1);
   \draw (9,0) -- (9,2);
   \draw[very thick] (9,0) -- (10,1);
   \draw (10,0) -- (10,3);
  \end{tikzpicture}

 \end{center}
\caption{Illustration of the last part of the proof of Claim 1. Slanted lines are sweeping counters
and grey areas are non-swept.}\label{figure:sweepVsNonSweep}
\end{figure}

At time $T_n$, a segment can contain a non-swept area longer than $\sqrt{n}$ only if it is issued from a segment longer than $\sqrt{n}$
initially, and the non-swept area of other segments have a density smaller than $\frac 1{\sqrt n}$. By $\s$-invariance,
$\mu(\{x\in\az\ |\ x_0\textrm{ is in a non-swept area}\}) \leq \frac 1{\sqrt n} + \mu(\Gamma^0_{\geq \sqrt n}) \underset{n\to\infty}\longrightarrow0$.\\

Therefore, for $a\in\A\backslash\B$, we have $\F^t\mu([a])\} \underset{t\to\infty}\to 0$.
\eclaimprf

\Claim{For any $n\in\N$, we have for $t$ large enough $\dm\left(\F^t\mu, Conv\left((w_i)_{i\geq n}\right)\right)\underset{t\to\infty}{\longrightarrow}0$, where $Conv(X)$ is the convex hull of the set $X$.}

\begin{figure}
 \begin{center}
  \begin{tikzpicture}[scale=1.4]
   \fill[black!20] (0,0) -- (0,1) -- (2,0) -- cycle (6,0) -- (10,0) -- (0,5) -- (0,3) -- cycle (10,2) -- (10,4) -- (8,5) -- (4,5) -- cycle;
   \draw[->] (-.5,-.5) -- (-.5,5.5);
   \draw (-.5, 5.8) node {time};
   \draw (-.6,0) -- (-.4,0) (-.6,2) -- (-.4,2) (-.6,4) -- (-.4,4);
   \draw (-1,0) node {$T_n$};
   \draw (-1,2) node {$T_{n+1}$};
   \draw (-1,4) node {$T_{n+2}$};
   \draw[<->] (0,-.3) -- (10,-.3);
   \draw[<->] (-1.5,0) -- (-1.5,5);
   \draw (5,-.6) node {$k$};
   \draw (-1.8,2.5) node {$k$};
   \draw[very thick] (0,-.2) -- (0,5.2) (10,-.2) -- (10,5.2);
   \draw[red,thick] (10,0) -- (0,5) (2,0) -- (0,1) (6,0) -- (0,3) (10,2) -- (4,5) (10,4) -- (8,5);
   \draw (.5,.25) node {$w_{n-3}$};
   \draw (2,1) node {$w_{n-2}$};
   \draw (4,2) node {$w_{n-1}$};
   \draw (6,3) node {$w_{n}$};
   \draw (8,4) node {$w_{n+1}$};
   \draw (9.5,4.75) node {$w_{n+2}$};
  \end{tikzpicture}
 \end{center}
\caption{Illustration of Claim 2. When $t>T_n+k$, the segment is a succession of stripes containing $w_n, w_{n+1},\dots$ plus a negligible part of auxiliary states and defects.}\label{figure:ConvexHull}
\end{figure}

\bclaimprf
Consider a segment of length $k$ at time $T_n$. At time $T_n+k$ the copying process for $w_n$ will be finished, but since the segment is not necessarily acceptable, other copying processes
may have started in the same segment. Therefore, the segment will be constituted by:
\begin{itemize}
 \item a negligible number of auxiliary states;
 \item strips containing repeated copies of $w_n$, then $w_{n+1}, w_{n+2}$\dots separated by ongoing copy processes (the number of auxiliary copy states being negligible). See Figure~\ref{figure:ConvexHull}.
\end{itemize}

Since the density of auxiliary states tends to 0, and $\mu(\Gamma^{T_n}_{l,\geq k}) \underset{k\to\infty}{\longrightarrow} 0$, for all $\varepsilon>0$ it is possible to take $k$ large enough so that $\dm\left(\F^{T_n+k}\mu, Conv((w_i)_{i\geq n})\right) < \varepsilon$.
\eclaimprf
The second point of the Theorem~\ref{MainTheorem} follows easily from Claim 2. \\

The use of a convex hull gives the intuition that, in order to reach a set of limit measures with this construction
(instead of a single measure), we have to control the length of the segments, which requires $\psi$-mixing; hence we do not hope to extend this
proof without modifying the construction in depth.

\section{Related problems solved with this construction}\label{section:RelatedProblem}

In this section, we use the construction developed in Theorem~\ref{MainTheorem} in view to solve natural problems concerning accumulation
point of the iteration of a cellular automaton on an initial measure.

\subsection{Characterization of the set of limit points}

\subsubsection{The connected case}
Reciprocals of the computable obstructions described in Section~\ref{section:ComputableObstruction} follow directly from Theorem~\ref{MainTheorem}.

\begin{corollary}\label{cor:ConvUniqueMeasure}
Let $\nu\in\Mreff(\bz)$ be a recursively computable measure. There is an alphabet $\A \supset \B$ and a cellular automaton $F:\az\to\az$ such that for any
$\mu \in \Mergfull(\az)$, one has $\lim_{n\to\N}\F\mu=\nu$.
\end{corollary}
If we furthermore suppose that the initial measure $\mu$ is computable, this is a full characterization of reachable measures $\nu$.

\begin{proof}
 Combine Proposition~\ref{prop:ApproximComputableMeasure} with the first point of Theorem~\ref{MainTheorem}.
\end{proof}

\begin{corollary}\label{cor:ConvSetMeasure}
Let $\add\subset \Ms(\B^\Z)$ be a compact, $\Sigma_2$-computable and connected ($\Sigma_2$-CCC) subset of $\Ms(\B^\Z)$. There is an alphabet $\A \supset \B$ and a cellular automaton $F:\az\to\az$ such that for
any $\mu \in \Mmixfull(\A^\Z)$, one has $\add(F,\mu) = \add$.
\end{corollary}
If we furthermore suppose that the initial measure $\mu$ is computable, this is a characterization of reachable connected subsets $\add$.
\begin{proof}
Combine Proposition~\ref{polygonalcover} with Theorem~\ref{MainTheorem}.
\end{proof}

\begin{open}
 Is it possible to improve the speed of convergence?
\end{open}

\subsubsection{Towards the non-connected case}
In Corollary~\ref{cor:ConvSetMeasure} it is assumed that the set is connected. It is due to the fact that in the construction of Theorem~\ref{MainTheorem},
the words $(w_n)_{n\in\N}$ are copied progressively and not instantaneously on each segment, so that we
get the closure of an infinite polygonal path, which is connected.
However, we get topological obstructions even if we consider a non-connected set of limit points. For example, if $\add(F,\mu)$
is finite one has the following proposition.

\begin{proposition}\label{prop:FiniteAdherenceValue}
 Let $F:\az\to\az$ be a cellular automaton and $\mu\in\Ms(\az)$ such that $\add(F,\mu)$ is finite. Then $\F$ induces a cycle on $\add(F,\mu)$.
\end{proposition}
\begin{proof}
Let $d=\min\{\dm(\nu,\nu'):\nu,\nu'\in\add(F,\mu)\textrm{ with }\nu\ne\nu'\}$ and consider $\nu\in\add(F,\mu)$. It is possible to extract a sequence
$(n_i)_{i\in\N}$ such that $\dm(\F^{n_i}\mu,\nu)<\frac{d}{3}$ and $\dm(\F^{n_i+1}\mu,\nu)>\frac{2d}{3}$. Since
$\dm(\F^n\mu,\add(F,\mu))\underset{n\to\infty}{\longrightarrow}0$, we have $\dm(\F^{n_i}\mu,\nu)\underset{i\to\infty}{\longrightarrow}0$. By continuity
of $\F$, $\dm(\F^{n_i+1}\mu,\F\nu)\underset{i\to\infty}{\longrightarrow}0$.

One deduces that for all $\nu\in\add(F,\mu)$ there exists $\nu'\in\add(F,\mu)$ such that $\F\nu=\nu'$. So there is $k\in\N$ such that $\add(F,\mu)=\{\nu_0,\dots,\nu_{k-1}\}$ and $\F\nu_i=\nu_{i+1}$ where the addition is modulo $k$.
\end{proof}

We exhibit some examples of more sophisticated behaviors based on the construction in Theorem~\ref{MainTheorem}. The first one is a family of cellular
automata where $\add(F,\mu)$ is a finite set of connected components, which is a partial reciprocal of Proposition~\ref{prop:FiniteAdherenceValue}.
The second one is a family of cellular automata where $\add(F,\mu)$ has an infinite number of connected components. However these are not total
characterizations of the possible set of limit points.

\begin{example}[Finite set of connected components]\label{example:finite}
Suppose $\add=\{\nu_0,\dots,\nu_{k-1}\}\subset\Ms(\bz)$ is a finite set of $\s$-invariant recursively computable measures such that $G\nu_i=\nu_{i+1}$
for some periodic cellular automaton $G:\bz\to\bz$. Then there is an alphabet $\A\supset\B$ and a cellular automaton $F:\az\to\az$ such that $\add(F,\mu)=\add$ for
$\mu\in\Mergfull(\A^\Z)$. Indeed, if $F$ is the cellular automaton which realizes $\nu_0$ obtained by Theorem~\ref{MainTheorem}, consider the cellular automaton that applies
$G$ on the output layer and applies the local rule of $F$ once every $k$ steps if an auxiliary state appears.

The same idea holds if $\add$ is a finite union of $\Sigma_2$-CCC sets which are mapped by a periodic cellular automaton $G:\bz\to\bz$.
\end{example}

\begin{example}[Infinite set of connected components]
We give some informal elements to modify the construction of Theorem~\ref{MainTheorem} to get examples of cellular automata where $\add(F,\mu)$ has an infinite number of connected components.
The construction uses the firing squad cellular automaton $(\B_{\texttt{FS}},F_{\texttt{FS}})$
which has the following properties: there exists four states $\left\{\fire,\block,\white,\order\right\}\subset\B_{\texttt{FS}}$ such that if
$x_{[0,n]}=\order\white^{n-1}\block$ then $F^{2n}_{\texttt{FS}}(x)_{[0,n]}=\fire^{n+1}$ and the state $\fire$ does not appear in
$(F^{i}_{\texttt{FS}}(x)_{j})_{(i,j)\in[0,n]\times[0,2n-1]}$\cite{Mazoyer-1996}.

Consider a computable family $(\add_i)_{i\in\N}$ of $\Sigma_2$-CCC subsets of $\Ms(\bz)$ and assume that $\add_i\cap\add_j=\emptyset$ for all $i,j\in\N$.
There is a computable sequence of words $(w_n)_{n\in\N}$ such that the limit points of this sequence are exactly $\add=\bigcup_{i\in\N}\add_i$.
Consider the cellular automaton $(\az,F)$ given by Theorem~\ref{MainTheorem} which produces $\add((w'_n)_{n\in\N})$ where $w'_n=w_n\times\white^{|w_n|}$,
with $\A\supset\B\times\B_{\texttt{FS}}$. We modify $F$ to obtain $\widetilde{F}$ in the following way:
\begin{itemize}
\item at time $T_n$, when the copy of $w_{n}$ is initiated, we initialize a counter on another layer to count the length $k$ of the segment;
\item at time $t=T_{n+1}-2k$, the state $\order$ appears on the left border of the segments (remember that the time counter keeps track of time);
\item All $\fire$ symbols are immediatly transformed into $\white$ symbols.
\end{itemize}

This requires the segments to be short enough, but the probability that $[0,l]$ belongs to such a segment tends to 1 as time tends to infinity (see Remark~\ref{rem:polynom}).
In those segments, $\widetilde{\F}\mu$ approximates the measure $\meas{w_n}\times\meas{\lfire}$ at time $T_{n+1}$ and the measure $\meas{w_n}\times\meas{\lwhite}$
at time $T_{n+1}+1$. The state $\fire$ appears only at times $(T_n)_{n\in\N}$.

For an initial measure $\mu\in\Mmixfull(\az)$, one has $\add(\widetilde{F},\mu)=\add\times\meas{\lfire}\cup\add'$ with
$\add'\subset\Ms\left(\left(\B_{\texttt{FS}}\setminus\{\fire\}\right)^\Z\right)$, which means it has an infinite number of connected components.
\end{example}

\begin{open}
Is it possible to characterize all compact subsets of $\Ms(\az)$ that can be reached as sets of limit points of the iteration of some cellular
automaton on a computable initial measure?
\end{open}

\subsection{Cesàro mean}

In this section, by adapting the enumeration $(w_n)$, we are able to get some control over the set $\add'(F,\mu)$ of limit points for the Cesàro
mean sequence.
\begin{corollary}\label{cor:ConvCesàroMeasure}
Let $\B$ be a finite alphabet and $\add'\subset \mes(\B^\Z)$ a $\Sigma_2$-CCC set.
There exists an alphabet $\A \supset \B$, and a cellular automaton $F:\A\to\A$ such
that for any $\mu \in \Mmixfull(\A^\Z)$, one has $\add'(F,\mu) = \add'$.
\end{corollary}

Remind that the latter is the set of limit points of the sequence $\varphi_t^F(\mu) = \frac 1{t+1} \sum_{i=0}^t\F^i\mu$.
$\add'(F,\mu)$ is necessarily connected (because $\mes(\az)$ is metric and compact), and if we suppose that the initial measure $\mu$ is computable,
we obtain a full characterization of reachable subsets $\add'$.\\

This corollary is a consequence of the following stronger result, where we have control over both $\add(F,\mu)$ and $\add'(F,\mu)$.

\begin{corollary}\label{cor:ConvCesàroMeasureBis}
Let $\B$ be a finite alphabet and $\add'\subset\add\subset \mes(\B^\Z)$ two $\Sigma_2$-CCC sets.
There exists an alphabet $\A \supset \B$, and a cellular automaton $F:\A\to\A$ such
that for any $\mu \in \Mmixfull(\A^\Z)$, one has
\begin{itemize}
 \item $\add(F,\mu) = \add$;
 \item $\add'(F,\mu) = \add'$.
\end{itemize}
\end{corollary}
$\add'(F,\mu)$ is necessarily included in the convex hull of $\add(F,\mu)$. Here we need a stronger hypothesis, namely, that it is included in
$\add(F,\mu)$. Therefore, if we suppose the initial measure is computable, this is a characterization of reachable pairs of connected subsets
$(\add,\add')$ such that $\add'\subset\add$.

\begin{proof} We will use notations from the proof of Proposition~\ref{polygonalcover}. Notably $(w_n)_{n\in\N}$ and $(w'_n)_{n\in\N}$ are the computable sequences of words associated
to $\add$ and $\add'$, respectively, and $\mathbf{V}_k^t = \{x\in\R_k : \exists T\leq t, f_t(x)<2\alpha_k\}$, where $f_t$ is a computable sequence satisfying $d_{\add} =
\liminf f_t$. Without loss of generality, suppose that $\max(|w_n|,|w'_n|)\leq \sqrt{n}$ for all $n$ (repeating some words if necessary).\\

We will define a new sequence of words $(w''_n)_{n\in\N}$ in the following manner, using a similar method as Proposition~\ref{polygonalcover}. For $i\in\N$, let $n_i$ be the maximal value such that
$\bigcup_{r\in\mathbf{V}_{n_i}^t}\B(r,\alpha_{n_i})$ has a path-connected component containing $\meas{w'_i},
\meas{w_i}$ and $\meas{w'_{i+1}}$. Let $P_i:[0,p_i]\to\mathbf{V}_{n_i}^t$ be a path in $\mathbf{V}_{n_i}^t$ such that
\begin{itemize}
 \item[-] $\dm(\meas{P_i(k)},\meas{P_i(k+1)})\leq\alpha_{n_i}$ for all $k\in[0,p_i-1]$;
 \item[-] $\dm(\meas{P_i(0)},\meas{w'_i})\leq\alpha_{n_i}$, $\dm(\meas{P_i(p_i)},\meas{w'_{i+1}})\leq\alpha_{n_i}$;
 \item[-] there exists $k\in[0,p_i]$ such that $\dm(\meas{P_i(k)},\meas{w_i})\leq\alpha_{n_i}$.
\end{itemize}
Since there are less than $|A|^{n_i}$ elements in $\mathbf{V}_{n_i}^t$, this path is of length $|P_i|\leq 2|A|^{n_i} \leq 2|A|^{|w_i|}<2|A|^i$.\\

For $n \in [|\A|^{i^2},|\A|^{(i+1)^2}]$, we define:
\begin{itemize}
 \item[-] if $n<|\A|^{i^2}+|P_i|,\ w''_n= P_i(n-|\A|^{i^2})$;
 \item[-] otherwise,\ $w''_n = w'_{i+1}$.
\end{itemize}

and let $F$ be the CA defined as in Theorem~\ref{MainTheorem}. Since all elements of $w_n$ are enumerated as in Proposition~\ref{polygonalcover}, we have
$\add(F,\mu) =
\add(w''_n) = \add$.\\

\begin{figure}[!ht]
 \begin{center}
  \begin{tikzpicture}
   \draw[->] (0,0) -- (14,0);
   \foreach \x\y in {0/0,4/T_{|\A|^{i^2}},5.5/T_{|\A|^{i^2}+|P_i|},13/T_{|\A|^{(i+1)^2}}}
   {
   \draw (\x,-0.2) -- (\x,0.2);
   \draw (\x,-0.5) node {$\y$};
   }
   \draw (0.3,-0.1) -- (0.3,0.1);
   \draw (0.2,-0.1) -- (0.2,0.1);
   \draw[<->] (0.1,0.2) -- (3.9,0.2);
   \draw[<->] (4.1,0.2) -- (5.4,0.2);
   \draw[<->] (5.6,0.2) -- (12.9,0.2);
   \draw (2,0.5) node {A} (2,-0.5) node {\small $w'_{i-1}$} (4.75,0.5) node {B} (9.25,0.5) node {C} (9.25,-0.5) node {\small $w'_i$};
  \end{tikzpicture}

 \end{center}
\caption{Intuitively, we prove $A+B\ll C$, then $B\ll A$.}
\end{figure}

We have \[\frac {|\A|^{i^2} +|P_i|}{|\A|^{(i+1)^2} - (|\A|^{i^2}+|P_i|)} < \frac{|\A|^{i^2+1}}{|\A|^{(i+1)^2} - |\A|^{i^2+1}}
\underset{i\to\infty}\longrightarrow 0.\]
In other words, the subset $[0,|\A|^{i^2} +|P_i|]$ is (asymptotically) of negligible density in $[0,|\A|^{(i+1)^2}]$.
Since $T_{n+1}-T_n$ is an increasing sequence, the subset $[0,T_{|\A|^{i^2} +|P_i|}]$ is of negligible density in $[0,T_{|\A|^{(i+1)^2}}]$. This means
that, putting $t_i
= T_{|\A|^{(i+1)^2}},d(\varphi_{t_i}^F(\mu), \meas{w'_{i+1}}) \underset{i\to\infty}\longrightarrow 0$.\\

Furthermore, notice that for $x,y\in \R_+$, when $y\leq \sqrt{x}$, we have $\lfloor \sqrt{x+y}\rfloor \leq \lfloor \sqrt{x}\rfloor +1$ and
$\lfloor \sqrt{x-y}\rfloor \geq \lfloor \sqrt{x}\rfloor -1$. Thus :
\[T_{|\A|^{i^2}+|P_i|}-T_{|\A|^{i^2}} < q^{|\A|^{\frac {i^2}2}+1}\cdot|\A|^i.\]  \[T_{|\A|^{i^2}} > T_{|\A|^{i^2}} -
T_{|\A|^{i^2}-|\A|^{\frac{i^2}2}} > q^{|\A|^{\frac {i^2}2}-1}\cdot|\A|^{\frac{i^2}2}\]
where $q$ is defined in Section~\ref{section:computation} and therefore \[\frac{T_{|\A|^{i^2} +|P_i|} - T_{|\A|^{i^2}}} {T_{|\A|^{i^2} +|P_i|}} \underset{i\to\infty}\longrightarrow 0.\]
This means that, when $t'_i = T_{|\A|^{i^2} +|P_i|},d(\varphi_{t'_i}^F(\mu), \meas{w'_i}) \underset{i\to\infty}\longrightarrow 0$.\\

The Cesàro mean sequence $\varphi_t^F(\mu)$ is (asymptotically) close to $\meas{w'_i}$ between times $t_i$ and $t'_i$, and is close to $\meas{w'_{i+1}}$ at time $t_{i+1}$.
Therefore, it is close to the segment $[\meas{w'_i},\meas{w'_{i+1}}]$ between times $t_i$ and $t_{i+1}$.
We conclude that asymptotically, the sequence is close to $\add((w'_n))$, and thus its set of limit points is $\add'$.
\end{proof}

\begin{open}
 Is it possible to extend Corollary~\ref{cor:ConvCesàroMeasureBis} when $\add'$ is not included in $\add$?
\end{open}

Using Example~\ref{example:finite} we can only provide some examples where $\add(F,\mu)\cap\add'(F,\mu)=\emptyset$.

\subsection{Decidability problem}

We give an undecidability result extending a result of Delacourt on $\mu$-limit sets \cite{Delacourt-2011}.

\begin{corollary}[Rice theorem on sets of limit measures]\label{cor:Rice}
Let $P$ be a property on set of measures that is nontrivial on
non-empty $\Sigma_2$-CCC sets
(i.e. not always or never true). Then it is undecidable, given a CA $F:\bz\to\bz$, whether $\add(F,\mu)$ satisfies $P$ for $\mu\in\Mmixfull(\bz)$.\end{corollary}

\begin{proof} We proceed by reduction to the halting problem.
Since $P$ is nontrivial, let $\add_1$ and $\add_2$ be two $\Sigma_2$-CCC sets that satisfies and does not satisfy $P$, respectively.
By Proposition~\ref{polygonalcover}, there exists two computable sequences of words $(w_n)_{n\in\N},(w'_n)_{n\in\N} \in (\A^{\ast})^\N$ such that $\add_1 = \add((w_n)_{n\in\N}), \add_2= \add((w'_n)_{n\in\N})$.

Now let $\mathcal{TM}$ be a Turing machine. Define the sequence $(w''_n)_{n\in\N}$ in the following way:
\begin{itemize}
 \item If $\mathcal{TM}$ halts on the empty input in $n$ steps, $w''_n = w_n$.
 \item Otherwise, $w''_n = w'_n$.
\end{itemize}
This sequence is computable by simulating $n$ steps of the Turing machine and computing the corresponding sequence. Therefore, we can use the previous construction to
build a CA $F$ such that $\add(F,\mu)= \add((w''_n)_{n\in\N})$. If $\mathcal{TM}$ halts on the empty input, then $w''_n = w_n$ for $n$ large enough; otherwise, $w''_n = w'_n$
for $n$ large enough. Thus, $\add(F,\mu)$ satisfies $P$ if and only if $\mathcal{TM}$ halts.
\end{proof}

The same reasoning holds for a single limit and the Ces\`aro mean sequence.

\begin{corollary}[Rice theorem for one limit measure]\label{cor:RiceSingle}
Let $P$ be a property on measures that is nontrivial
on recursively computable measures.
Then it is undecidable, given a CA $F:\bz\to\bz$, whether $\F^t\mu \to \nu$
where $\nu$ satisfies $P$ for $\mu\in\Mmixfull(\bz)$.
\end{corollary}

\begin{corollary}[Rice theorem on Ces\`aro mean]\label{cor:RiceCesaro}
Let $P$ be a property on set of measures that is nontrivial on
non-empty $\Sigma_2$-CCC sets. Then it is undecidable, given a CA $F:\bz\to\bz$, whether $\add'(F,\mu)$ satisfies $P$ for $\mu\in\Mmixfull(\bz)$.
\end{corollary}

\subsection{Computation on the set of measures}\label{section:Oracle}

In this section the construction developed in section~\ref{section:Construction} is modified to perform computation on the space of probability measures.
In other words, we want the set of limit points to be a function of the initial measure.

\subsubsection{Computation with oracle}
The definitions of Section~\ref{section:ComputableObstruction} can be adapted to compute with an oracle $\mu\in\Ms(\az)$.

A \define{Turing machine with oracle} in $\mathcal{M}\subset\Ms(\az)$ has the same behavior as a classical Turing machine but it takes initially in argument a measure $\mu\in\mathcal{M}$ as oracle. During the computation it can query the oracle by writing $u\in\A^\ast$ and $n\in\N$ on an additional \define{oracle tape} and entering a special oracle state. Then the oracle writes an approximation of $\mu([u])$ with an error $2^{-n}$ and the computation continues.

Let $\mathcal{M}\subset\Ms(\az)$ and $X,Y$ two enumerable sets. A function $f:\mathcal{M}\times X\to Y$ is \define{computable with oracle in $\mathcal{M}$} if there exists a Turing machine with oracle in $\mathcal{M}$ which takes as input $x\in X$ and returns $y=f(\mu,x)\in Y$, up to reasonable encoding.

\begin{definition}
Let $\mathcal{M}\subset\Ms(\az)$.

A function $\varphi:\mathcal{M}\longrightarrow\Ms(\bz)$ is \define{computable with oracle} in $\mathcal{M}$ if there exists $f:\mathcal{M}\times \N\longrightarrow\B^{\ast}$
a computable function with oracle in $\mathcal{M}$ such that $|\varphi(\mu)-\meas{f(\mu,n)}|\leq 2^{-n}$. This is an extension of the previous definition where the image is not
countable, hence the abuse of notation.

A function $\varphi:\mathcal{M}\longrightarrow\Ms(\bz)$ is \define{recursively computable with oracle} in $\mathcal{M}$ if there exists $f:\mathcal{M}\times \N\longrightarrow
\B^{\ast}$ a computable function with oracle in $\mathcal{M}$ such that $\meas{f(\mu,n)}\underset{n\to\infty}{\longrightarrow}\varphi(\mu)$.

A sequence of functions $(f_n:\mathcal{M}\times\Ms(\az)\longrightarrow\R)_{n\in\N}$ is \define{a computable sequence of functions with oracle in $\mathcal{M}$} if
\begin{itemize}
\item there exists  $a:\mathcal{M}\times\N\times\N\times\A^{\ast}\longrightarrow\Q$ computable with oracle in $\mathcal M$ such that  $\left|f_n(\mu,\meas{w})-a(\mu,n,m,w)\right|
\leq\frac{1}{m}$ for all $\mu\in\mathcal{M}$, $w\in\A^{\ast}$ and $n,m\in\N$;
\item there exists $b:\mathcal{M}\times\N\longrightarrow\Q$ computable with oracle in $\mathcal M$ such that $\dm(\nu,\nu')<b(\mu,m)$ implies $\left|f_n(\mu,\nu)-f_n(\mu,\nu')\right
|\leq\frac{1}{m}$ for all $\mu\in\mathcal{M}$ and $n,m\in\N$.
\end{itemize}

Let $\mathfrak{K}$ be a set of compact subsets of $\Ms(\bz)$. A function $\add:\mathcal{M}\longrightarrow\mathfrak{K}$ is \define{$\Sigma_2$-computable with oracle in $\mathcal{M}$} if there exists a computable sequence of
functions $(f_n:\mathcal{M}\times\Ms(\bz)\longrightarrow\R)_{n\in\N}$ with oracle in $\mathcal{M}$ such that $d_{\add(\mu)}(\nu)=\liminf_{n\to\infty}f_n(\mu,\nu)$
for all $\nu\in\Ms(\bz)$.

\end{definition}

The proofs of Section~\ref{section:ComputableObstruction} can be easily adapted in this framework. For any cellular automaton $F$ on $\az$, one has:
\begin{itemize}
\item following Proposition~\ref{prop:OneStep}, the function $\mu\longmapsto\F\mu$ is computable with oracle in $\Ms(\az)$;\item following Proposition~\ref{prop:add=s2ccc}, $\mu\longmapsto\add(F,\mu)$ and $\mu\longmapsto\add'(F,\mu)$ are $\Sigma_2$-computable
with oracle in $\Ms(\az)$;
\item following Proposition~\ref{polygonalcover}, if $\add:\mathcal{M}\longrightarrow\mathfrak{K}$ is a $\Sigma_2$-computable function with oracle in $\mathcal{M}$ and
if every element of $\mathfrak{K}$ is connected, then there exists a computable function $f:\mathcal{M}\times\N\longrightarrow\A^{\ast}$ with oracle in $\mathcal{M}$ such that
$\add(\mu)=\add((f(\mu,n))_{n\in\N})= \bigcap_{N>0}\overline{\bigcup_{n\geq N}\left[\meas{f(\mu,n)},\meas{f(\mu,n+1)}\right]}$.
\end{itemize}

\subsubsection{Towards a reciprocal}
In this section, we give a partial reciprocal to the last fact. To use the initial measure $\mu\in\Ms(\az)$ as an oracle, we need to keep some information from the initial configuration. We adapt the original construction in the following way:\\

Each segment keeps a sample of the initial configuration, using the frequency of patterns this sample as an oracle in the computation.
We need to ensure that the frequency of a pattern $u\in\A^k$ in this sample is
close to $\mu([u])$ with a high probability. For $\mu\in\Mmixfull(\az)$ we have an exponential rate of convergence for
every length (Theorem~III.1.7 of~\cite{Shields-1996}). More precisely:
\[\mu\left(\left\{x\in\az : \max_{u\in\A^k}\{ |\mu([u])-\textrm{Freq}(u,x_{[0,n]})|\geq \varepsilon\}\right\}\right)\leq(k+m)\psi(m)^{\frac{n}{k}}\left(\frac{n}{k}+1\right)^{\textrm{Card}(A)^k}
2^{-\frac{nc\varepsilon^2}{4k}} ,\]
where $m\in\N$, $c>0$ and $\textrm{Freq}(u,x_{[0,n]})=\frac{1}{n+1}\textrm{Card}\left(i\in[0,n]:x_{[i,i+|u|-x]}=u\right)$ is the \define{frequency} of $u$ in the pattern $x_{[0,n]}$.

However, in our case, not all the information in the initial configuration can be kept since sweeping destroys information in the segment.
Therefore, we will keep partial information from $\pi\mu$, where $\pi:\az\longrightarrow\{0,1\}^{\Z}$ is a 1-block map such that
$\pi\left(\hspace{-0.1cm\right)=1$ and $\pi(a)=0$ otherwise.
Even then, remembering the frequencies of all words takes too much space, so we just keep information about words of a fixed length. Here, each segment will keep in memory only the density of one letter,
but it is possible to adapt it to keep information on longer words.

\begin{theorem}\label{theorem:Computable}
Let $\add:\Mmixfull(\{0,1\}^{\Z})\to\mathfrak{K}$ be a $\Sigma_2$-computable function where $\mathfrak{K}$ is a set of compact connected
subsets of $\Ms(\bz)$.
Assume that $\add(\mu)=\add(\mu')$ if $\mu([1])=\mu'([1])$ for $\mu,\mu'\in\Mmixfull(\{0,1\}^{\Z})$.

There exists a cellular automaton $(\az,F)$ such that $\add(F,\mu)=\add(\pi\mu)$ for all $\mu\in\Mpsimix(\az)$ where $\pi:\az\longrightarrow\{0,1\}^{\Z}$
is the 1-block map defined above.\end{theorem}

Notice that since only one density is considered, it would be equivalent to consider a $\Sigma_2$-computable function $\R\to\mathfrak{K}$.
\begin{proof}
Let $f:\mathcal{M}\times\N\longrightarrow\A^{\ast}$ be a computable function with oracle in $\mathcal{M}$ such that $\add(\mu)=\add((f(\mu,n))_{n\in\N})$
and consider the associated Turing machine with oracle.

Consider the cellular automaton defined in the proof of Theorem~\ref{MainTheorem}. We add a new layer $\alph{oracle}$ in which each segment at time $t$ stores the frequency of the state $\hspace{-0.1cm$ in this segment at time 0. To do that, we modify the construction in the following way:
\begin{itemize}
 \item We subdivide the layer $\alph{oracle}$ in two parts, on which each wall $\hspace{-0.1cm$ keeps on its left:
\begin{itemize}
 \item the first counter for the number of $\hspace{-0.1cm$ symbols that have been destroyed in its left segment;
 \item the second counter for its length, worth 0 if the segment is not swept.
 \end{itemize}
\item Another counter accompanies each sweeping counter, measuring the length of the segment as it progresses.
\item The second counter is initialized as $0$. When the time counter attached to this wall makes a comparison with an initialized sweeping counter (the comparison returns the result ``=''), the second counter stores the length of the segment. It may take the value $0$ again after merging with a non-swept segment (see below).
\item When a wall is destroyed by a merging process, it sends to its right a signal at speed~$1$ containing all the stored information. Such a signal should not cross a sweeping counter, so it is slowed down if necessary.
\item When a wall has stored $(c_1,c_2)$ as oracle and receives the signal $(c'_1,c'_2)$ from its left, there are three cases:
\begin{itemize}
 \item If $c_2=0$, the left segment was not swept, the signal cannot come from an initialized wall and can be safely ignored. The oracle remains $(c_1,c_2)$.
 \item If $c_2\ne 0$, the information comes from an initialized wall. Put $c''_1=c_1+c'_1+1$ to take the merging into account. If $c'_2=0$, the segment just merged with a non swept segment and $c''_2=0$; otherwise $c''_2=c_2+c'_2$. The new oracle is $(c''_1,c''_2)$.
\end{itemize}
See Figure~\ref{figure:OracleCounter}. We remark that if the length of the segment is $k$, the information can be coded in space $\log(k)$, and it is possible to actualize the values before
another signal can come from the left.

\begin{figure}[!ht]
 \begin{center}
  \begin{tikzpicture}
  \draw[->] (-.7,-.5) -- (-.7,5.5);
  \draw (-.7,5.8) node {time};
  \draw (-.8,3) -- (-.6,3);
  \draw (-1,3) node {$T_n$};
   \foreach \t in {0,6,14}
   {
   \draw[very thick] (\t,-.2) -- (\t,5.5);
   \draw (\t-.35,0) node {\footnotesize{$0,0$}};
   }
   \foreach \t in {3,4.5,12.5}
   {
   \draw[very thick] (\t,-0.2) -- (\t,3);
   \draw (\t-.35,0) node {\footnotesize{$0,0$}};
   }
   \foreach \a\c in {0/3,3/4.5,4.5/6,6/13.5,12.5/14}
   \draw[thick] (\a,0) -- (\c,0.7*\c-0.7*\a);
   \draw (2.65,2.3) node {\footnotesize{$0,k$}};
   \draw (4.15,1.25) node {\footnotesize{$0,n$}};
   \draw (5.65,1.25) node {\footnotesize{$0,n$}};
   \draw (13.65,1.25) node {\footnotesize{$0,n$}};
   \foreach \a\b\c in {3/6,4.5/6,12.5/14}
   \draw[thick,dotted] (\a,3) -- (\c,0.7*\c-0.7*\a+3);
   \draw (5.55,4.2) node {\footnotesize{$1,2n$}};
   \draw (5.3,5.3) node {\footnotesize{$2,2n+k$}};
   \draw (13.65,4.2) node {\footnotesize{$1,0$}};
   \draw[<->] (0,-.4) -- (3,-.4);
   \draw (1.5,-.6) node {$k$};
   \draw[<->] (4.5,-.4) -- (6,-.4);
   \draw (5.25,-.6) node {$n$};
  \end{tikzpicture}
 \end{center}
 \caption{Each wall has its counter displayed when its value changes. Slanted thick lines are sweeping counters, dotted lines are signals transmitting information.}
\label{figure:OracleCounter}
 \end{figure}

\item If two symbols $\hspace{-0.1cm$ are too close in the initial configuration, they are destroyed by the bootstrapping process (see Section~\ref{section:bootstrapping}). If a $\hspace{-0.1cm$ is in a group of $\hspace{-0.1cm$ separated by two cells or less, the rightmost $\hspace{-0.1cm$ sends a sweeping counter and the leftmost one starts a time counter. Thus a group of $\hspace{-0.1cm$ separated by two cells or less behave as a single symbol for initialization purposes. All the $\hspace{-0.1cm$ except the leftmost one are transformed immediately into oracle signals (supposing the basis of the counter is larger than 3 then they occupy only one cell) and the other cells present initially are erased.
\item The Turing machine simulation described in Section~\ref{section:computation} can be adapted to simulate a Turing machine with oracle. When there is an oracle query
for the value of $\mu([\hspace{-0.1cm])$ with the precision $2^{-i}$ at time $t\in [T_n,T_{n+1}]$, there are two possibilities:
\begin{itemize}
\item if $n^{-\frac{1}{6}}\leq 2^{-i}$, the Turing machine uses the information stored in the oracle layer to return the frequency of $\hspace{-0.1cm$ on the segment at time 0,
and this corresponds to an approximation of $\mu([\hspace{-0.1cm])$ with sufficient precision;
\item if $n^{-\frac{1}{6}}  > 2^{-i}$, the computation stops, and the previously computed word will be copied at time $T_{n+1}$. The same thing happens until time $T_i$,
when enough information will be available.
\end{itemize}
\end{itemize}

Let us check that $\add(\pi\mu)=\add(F,\mu)$ for $\mu\in\Mmixfull(\az)$. It is clear that the density of auxiliary states tends to 0,
so if the sample approximates correctly $\mu([\hspace{-0.1cm])$, the sequence of words $(w_n)_{n\in\N}$ produced by the cellular automaton correspond to $(f(\mu,n))_{n\in\N}$
up to some repetition. Thus we only need to prove that the probability that a cell belongs to a segment which sample
correspond to a ``bad'' approximation tends to $0$ when $t$ tends to $\infty$.
Recall that $\Gamma^{T_n}_{[i,j]} = \{x\in\az\ |\ [i,j]$ is a segment at time $T_n\}$.

\begin{align*}
 B_n&\phantom{=}=&&\mu\left(\left\{x\in\az : x_0\textrm{ belongs in a segment with a ``bad'' sample at time }T_n \right\}\right)\\
&\phantom{=}=&&\sum_{i<0,j>0}\mu\left(\left\{x\in \Gamma^{T_n}_{[i,j]} : |\mu([u]) - Freq(u,x_{[i,j]})|>n^{-\frac 16}\right\}\right)\\
&\phantom{=}=&&\sum_{k>0}k\cdot\mu\left(\left\{x\in\Gamma^{T_n}_{[0,k]} : |\mu([u]) - Freq(u,x_{[0,k]})|>n^{-\frac 16}\right\}\right),
\end{align*}
by $\s$-invariance. By restricting ourselves to $n\leq k\leq K_n$:
\begin{align*}
 B_n&\phantom{=}\leq&&\mu\left(\Gamma^{T_n}_{0,\geq K_n}\right)+\sum_{k=n}^{K_n}k\cdot\mu\left(\left\{x\in\az : |\mu([u]) - Freq(u,x_{[0,k]})|>n^{-\frac 16}\right\}\right)\\
 &\phantom{=}\leq&& \mu\left(\Gamma^{T_n}_{0,\geq K_n}\right)+ K_n^2(1+m)\psi(m)^n\left(n+1\right)^{\textrm{Card}(A)}2^{-\frac{c}{4}n^{\frac{2}{3}}}\\
 &\underset{n\to\infty}{\longrightarrow}&&0.
 \end{align*}

The result follows.

\end{proof}

This result may seem surprising since the same cellular automaton has very different asymptotical behaviors depending on the initial measure.
\begin{open}
Is it possible to improve Theorem~\ref{theorem:Computable} and characterize functions
$f:\mathcal{M}^{\textrm{full}}_{\psi-\textrm{mix}}(\{0,1\}^{\Z})\to\mathfrak{K}$, where $\mathfrak{K}$ is a set of compact
subsets of $\Ms(\bz)$, that are realisable as the action of a cellular automaton $F$ in the sense that for all $\mu$, $\add(F,\mu) = f(\mu)$?
\end{open}

\section{Removing the auxiliary states}\label{section:NoAux}

In this section, our aim is to carry the previous results to the case where the cellular automaton does not use auxiliary states. A straightforward extension is impossible: for example, consider $\nu$ a
recursively computable measure with full support and $F : \az \to \az$ a cellular automaton such that $\F\mu\to\nu$ when $\mu$ is a ``simple'' measure. Since $\nu$ has full support,
$F$ is a surjective automaton, and hence the uniform Bernoulli measure is invariant under $\F$. Thus $\nu$ must be the uniform Bernoulli measure.\\

However, if the limit measure does not have full support, the previous results can be extended by using a word not charged by the measure to encode the auxiliary states
in some sense.

\begin{theorem}\label{MainTheoremNoAux}
Let $(w_n)_{n\in\N}$ be a computable sequence of words of $\B^{\ast}$, where $\B$ is a finite alphabet, and let $u\in\B^\ast$ a word that
does not appear as factor in any of the $w_n$. Then there is a cellular automaton $F : \B^{\Z}\to \B^{\Z}$ such that
for any measure $\mu \in \Mmixfull(\B^\Z)$, $\add(F,\mu) = \add((w_n)_{n\in\N})$.
\end{theorem}
\begin{proof}

Let $\A$ be the alphabet and $F$ be the CA associated to the sequence $(w_n)_{n\in\N}$ by Theorem~\ref{MainTheorem}. Our aim is to provide an encoding of any configuration
of $\az$ in $\bz$ and a cellular automaton $F'$ that behaves similarly to $F$ after encoding.\\

Denote $U_d \subset \B^d$ be the set of words of length $d$ beginning with $u$, that do not contain $u$ as factor (except at the first letter), and that do not end
with a prefix of $u$.
$\#(U_d) \underset{d\to\infty}\longrightarrow \infty$, so for $d$ large enough, we can find an injection $\varphi : \A\backslash\B \to U_d$,
and we extend it by putting $\varphi = Id$ on $\B$.
For a finite word, we define $\varphi(u_1\dots u_n) = \varphi(u_1)\dots\varphi(u_n)$, and this can be naturally extended further to configurations $\Phi:\A^\Z\mapsto \B^\Z$
by considering that $\varphi(a_0)$ starts on the column zero.\\

Let $\mathbf{T}\subset\az$ be the set of configurations such that the word $u$ does not appear on the output layer ($\mathbf{T}$ is a subshift of finite type).  Since $u$ marks unambiguously the beginning of a word of $\varphi(\A\backslash\B)$, the restriction $\Phi:\mathbf{T}\to\bz$ is injective.

Each configuration from $\B^\Z$ can thus be divided uniquely into words from $\varphi(\A)$, that we will call \define{clusters} from now on.
\define{Output cells} are elements of $\B=\varphi(\B)$ that occupy only 1 cell (corresponding to $(b,\#,\#,\#,\#,\#)$ for $b\in \B$ in the previous construction) and \define{auxiliary clusters} are elements of $\varphi(A\backslash B)$ that occupy $d$ cells while containing one letter of output. Thus we can define a decoding $\Psi:\bz\to\mathbf{T}$ such that $\Psi\circ\Phi=\textrm{Id}$.

However, $\Phi$ and $\Psi$ are not $\sigma$-invariant, so $\Phi\circ F\circ\Psi$ is not a cellular automaton. We must build manually a cellular automaton on $\B^\Z$ that behaves in roughly the same way as $\Phi\circ F\circ \Psi$. Provided the neighborhood is larger than $[-4d,4d]$, each cell can ``read" the cluster in which it belongs, and the three clusters to its right and left.

If a word $u$ appears outside of an auxiliary cluster, it is replaced by some output cells and can never be created again.
 To avoid creating an auxiliary cluster by mistake, we fix to this purpose a letter $b\in\B$ such that $b^d\notin U_d$.
 Similarly, auxiliary clusters that are destroyed for any reason leave behind them output $b$ cells.

The different parts of the construction are modified in the following way.

\begin{itemize}
 \item $\hspace{-0.1cm$ and $\hspace{-0.1cm$ clusters, time counters, and Turing machines have the same behavior as in the previous construction.
 However, since the counters take more space, it is necessary to erase $3d$ cells to the left and right of each $\hspace{-0.1cm$ cluster at time 0.

 \item The copying process progresses to the left at speed one, and behaves normally as long as it does not meet another auxiliary state (see Figure~\ref{fig:NoAuxCopy}).

\begin{figure}[!ht]
\begin{center}
 \begin{tikzpicture}[scale=1.2]

\foreach \t in {0,...,5}
{
\filldraw[fill=black!20] (-8,\t) rectangle (-10.4,\t+0.8);
\draw (-9.2,\t +.4) node {W};
}

\foreach \x\y\z\t in {0/0/1/1,3/0/1/0,1/1/1/0,4/1/1/1,2/2/0/1,5/2/1/1,3/3/1/1,6/3/0/1,4/4/1/1,7/4/1/0,5/5/1/0}
{
 \draw (-0.8*\x,\y+0.4) rectangle (-0.8*\x-2.4,\y+0.8);
 \draw (-0.8*\x-0.8,\y) rectangle (-0.8*\x-1.6,\y+0.4);
 \draw (-0.8*\x-1.2,\y+0.6) node {\z};
 \draw (-0.8*\x-1.2,\y+0.2) node {\t};
}

\foreach \x\y\z in {6/0/?,7/0/?,8/0/?,9/0/?,0/1/1,7/1/?,8/1/?,9/1/?,0/2/1,1/2/0,8/2/?,9/2/?,0/3/1,1/3/0,2/3/1,9/3/?,0/4/1,1/4/0,2/4/1,3/4/1,
0/5/1,1/5/0,2/5/1,3/5/1,4/5/1,8/5/0,9/5/0}
{
\draw (-0.8*\x,\y) rectangle (-0.8*\x-0.8,\y+0.8);
\draw (-0.8*\x-.4,\y+.4) node {\z};
}

\draw (1,2.9) rectangle (4,3.4);
\draw (2,2.4) rectangle (3,2.9);
\draw (2.5,2.15) node {\small{output}} ;
\draw (2.5,3.55) node {\small{copy}} ;

\end{tikzpicture}
\end{center}
\caption{End of the copying process described in Figure~\ref{figure:copy}, copying 1101.}
\label{fig:NoAuxCopy}
\end{figure}

 \item Sweeping counters progress to the right at speed $d$. This is too fast to keep the output information, so the counter leaves behind output cells $b$ defined above. Any moving signal it meets (e.g. copying process or length signal) is destroyed. When entering the time counter, if it cannot progress by $d$ cells exactly,
 it is offset by less than $d$ cells (see Figure~\ref{fig:SweepOffset}). Thus sweeping clusters separated by small offsets are still considered to be the same counter.

\begin{figure}[!ht]
\begin{center}
 \begin{tikzpicture}[every text node part/.style={align=center},scale=1.2]
\foreach \x\y\z in {0/0/time,3/0/time,10/0/sweeping,13/0/sweeping,0/1/time,3/1/time,0/2/time,7/1/sweeping,10/1/sweeping,
3/2/time\\sweeping,7/2/sweeping,0/3/time\\sweeping,3/3/time\\sweeping}
{
 \draw (-0.8*\x,\y) rectangle (-0.8*\x-2.4,\y+0.8);
 \draw (-0.8*\x-1.2,\y+0.4) node {\z};
}

\foreach \x\y\z in {6/0,7/0,8/0,9/0,6/1,6/2,6/3}
{
\draw (-0.8*\x,\y) rectangle (-0.8*\x-0.8,\y+0.8);
\draw (-0.8*\x-.4,\y+.4) node[text width=.1cm] {?};
}

\foreach \x\y\z in {13/1,14/1,15/1,10/2,11/2,12/2,13/2,14/2,15/2,
7/3,8/3,9/3,10/3,11/3,12/3,13/3,14/3,15/3}
{
\draw (-0.8*\x,\y) rectangle (-0.8*\x-0.8,\y+0.8);
\draw (-0.8*\x-.4,\y+.4) node[text width=.1cm] {$0$};
}
\end{tikzpicture}
\end{center}
\caption{A sweeping counter gets offset when entering the computation / time counter area. Notice the output cells are replaced by zeroes.}
\label{fig:SweepOffset}
\end{figure}

\item Merging signals which determine length of segments also progress at speed $d$. To avoid being offset by copying processes (which would modify the ``measured length''), the determination
 of length starts only after the copy is finished. Thus the signal is only offset once, when entering the time counter area. After bouncing off the right wall, it returns to
 the left wall where its offset can be measured. If it takes $t_0$ steps to return with an offset of $\alpha$, then the segment has length $\frac {t_0}2\cdot d+\alpha$
 (see Figure~\ref{fig:LengthOffset}). On the left side of the wall, a Turing machine computes the measured length and compares it with $n$, and a $\hspace{-0.1cm$ symbol is created if needed.

\begin{figure}[!ht]
\begin{center}
 \begin{tikzpicture}[every text node part/.style={align=center},scale=1.2]
\foreach \x in {-1,...,6}
{
\filldraw[fill=black!20] (-10.4,\x) rectangle (-12.8,\x+0.8);
\draw (-11.6,\x+.4) node {W};
\filldraw[fill=black!20] (0,\x) rectangle (2.4,\x+0.8);
\draw (1.2,\x+.4) node {W};
}

\foreach \x\y in {0/-1,3/-1,0/0,3/0,0/1,3/2,3/3,0/4,0/5,3/5,0/6,3/6}
{
 \draw (-0.8*\x,\y) rectangle (-0.8*\x-2.4,\y+0.8);
 \draw (-0.8*\x-1.2,\y+0.4) node {time};
}

\foreach \x\y in {10/-1, 7/0}
{
 \draw (-0.8*\x,\y) rectangle (-0.8*\x-2.4,\y+0.8);
 \draw[thick, ->] (-0.8*\x-1.8,\y+0.2) -- (-0.8*\x-0.6,\y+0.6);
}

\foreach \x\y in {6/5, 9/6}
{
 \draw (-0.8*\x,\y) rectangle (-0.8*\x-2.4,\y+0.8);
 \draw[thick, ->] (-0.8*\x-0.6,\y+0.2) -- (-0.8*\x-1.8,\y+0.6);
}

\foreach \x\y in {3/1,0/2}
{
 \draw (-0.8*\x,\y) rectangle (-0.8*\x-2.4,\y+0.8);
 \draw (-0.8*\x-1.2,\y+0.4) node {time};
 \draw[thick, ->] (-0.8*\x-1.8,\y+0.2) -- (-0.8*\x-0.6,\y+0.6);
}

\foreach \x\y in {0/3, 3/4}
{
 \draw (-0.8*\x,\y) rectangle (-0.8*\x-2.4,\y+0.8);
 \draw (-0.8*\x-1.2,\y+0.4) node {time};
 \draw[thick, ->] (-0.8*\x-0.6,\y+0.2) -- (-0.8*\x-1.8,\y+0.6);
}

\foreach \x\y in {6/-1,7/-1,8/-1,9/-1,6/0,10/0,11/0,12/0,6/1,10/1,11/1,12/1,6/2,10/2,11/2,12/2,6/3,10/3,11/3,12/3,6/4,10/4,11/4,12/4,10/5,11/5,12/5,7/6,8/6,12/6}
{
\draw (-0.8*\x,\y) rectangle (-0.8*\x-0.8,\y+0.8);
\draw (-0.8*\x-.45,\y+.4) node[text width=.1cm] {?};
}

\foreach \x\y in {7/1,8/1,9/1,7/2,8/2,9/2,7/3,8/3,9/3,7/4,8/4,9/4,9/5,6/6}
{
\draw (-0.8*\x,\y) rectangle (-0.8*\x-0.8,\y+0.8);
\draw (-0.8*\x-.45,\y+.4) node[text width=.1cm] {0};
}
\end{tikzpicture}
\end{center}
\caption{Determination of length. Here $d=3,\,t_0 = 8$ and $o=1$, for a measured length of 13.}
\label{fig:LengthOffset}
\end{figure}

 \end{itemize}
 \begin{remark} For clarity, in all diagrams of this section, we suppose that $\B = \{0,1\}$, $d=3$ (it would be much larger in real implementations) and we represent auxiliary clusters as blocks with layers, instead of words from $\B^d$. Also we fix $b=0$ in the definition above. \end{remark}

The bootstraping and sweeping processes work essentially in the same way as previously, except that a sweeping counter erases any copy process and merging signal it meets, along with output information.
Hence Propositions \ref{prop:AcceptableIsSwept} and \ref{prop:AllAcceptable} can be extended. Furthermore, at time $t$, with $T_n\leq t <T_{n+1}$,
the copy process followed by the process of determination of length for segments of size $n+1$ still take less than $T_{n+1}-T_n$ steps. Hence the proof in section
\ref{section:FirstPoint} can be extended, and the theorem follows.
\end{proof}

However, because of the destructive nature of the sweeping counter, the proof in section \ref{section:SecondPoint}
cannot be adapted and we cannot weaken the hypothesis to $\mu \in \Mergfull(\B^\Z)$ when $\add$ is a singleton. Since this result is a counterpart to
the second point of Theorem~\ref{MainTheorem} that does not use auxiliary states, it is natural to give similar counterparts to
corollaries~\ref{cor:ConvSetMeasure} to \ref{cor:RiceCesaro}.
\begin{definition}
A word $u\in\A^\ast$ is said to be \define{not charged} by a set $\add\in\Ms(\az)$ if for all $\nu\in\add$, $\nu([u]) = 0$.
\end{definition}

\begin{corollary}\label{cor:ConvSetMeasureNoAux}
Let $\add\subset \Ms(\B^\Z)$ be a non-empty $\Sigma_2$-CCC subset of $\Ms(\B^\Z)$ that does not charge a word $u\in\B^\ast$.
Then there is a cellular automaton $F:\bz\to\bz$ such that for
any measure $\mu \in \Mmixfull(\B^\Z)$, $\add(F,\mu) = \add$.
In particular, any recursively computable measure which does not have full support can be obtained this way.
\end{corollary}
\begin{proof}
Since $\add$ does not charge $u$, we can assume without loss of generality that no word in the computable sequence $(w_n)_{n\in\N}$ associated to $\add$ by
Proposition~\ref{prop:ApproximComputableMeasure} contains $u$ as factor. Thus Theorem~\ref{MainTheoremNoAux} applies.
\end{proof}

The proofs of the following corollaries are adaptations of the proofs of their counterparts using Theorem~\ref{MainTheoremNoAux}.
Of course Corollary~\ref{cor:ConvUniqueMeasure} does not have a counterpart since its proof uses the first point of Theorem~\ref{MainTheorem}.

\begin{corollary}\label{cor:ConvCesaroMeasureNoAux}
Let $\add'\subset\add\subset \mes(\B^\Z)$ two non-empty $\Sigma_2$-CCC sets that both do not charge the same word $u\in\B^\ast$.
Then there exists a cellular automaton $F:\B\to\B$ such
that for any $\mu \in \Mmixfull(\A^\Z)$,
\begin{itemize}
 \item $\add(F,\mu) = \add$;
 \item $\add'(F,\mu) = \add'$.
\end{itemize}
\end{corollary}

\begin{corollary}[Rice theorem on sets of limit measures]\label{cor:RiceNoAux}
Let $\B$ be a fixed alphabet, $\mu \in \Mmixfull(\B^\Z)$, $u\in\B^\ast$, and $P$ be a property on set
of measures that is nontrivial (i.e. not always or never true)
on non-empty $\Sigma_2$-CCC sets that do not charge $u$. Then it is undecidable, given a CA $F:\bz\to\bz$, whether $\add(F,\mu)$ satisfies $P$.
\end{corollary}

This result extends to single measures and limit points of Ces\`aro mean sequence, in a similar way as Corollaries~\ref{cor:RiceSingle} and \ref{cor:RiceCesaro}.\\

We leave open in particular the case of limit measures with full support. For corollaries~\ref{cor:ConvSetMeasureNoAux} and
\ref{cor:ConvCesaroMeasureNoAux},
solving this case would imply to characterize the possible asymptotic behaviors of surjective automata, for which a similar construction seems difficult.
As for Corollary~\ref{cor:RiceNoAux}, if we fix $\mu$ the uniform Bernoulli measure, the problem of whether $\add(F,\mu)$ contains only the uniform Bernoulli measure
is equivalent to the surjectivity of $F$, which is decidable \cite{Amoroso-1972}. Hence the question of which nontrivial properties on limit measures and sets of limit measures
with full support are decidable remains open.

\begin{open}
 Which sets of measures are reachable by surjective cellular automata?
\end{open}