Figure 8. The Toom rule’s effect on a large triangular island

######  Remark 5.3.

The notion of ergodicity was defined only for trajectories of
$R_{\varepsilon}$ that are also trajectories of some probabilistic cellular
automaton $R^{\prime}$ (as defined in Subsection 2.3) such that
$R^{\prime}\subset R_{\varepsilon}$, i.e. that all trajectories of
$R^{\prime}$ are trajectories of $R_{\varepsilon}$. The difference between
$R_{\varepsilon}$ and $R^{\prime}$ is that the local transition probabilities
of a trajectory of $R^{\prime}$ are fixed and the same everywhere in space-
time, while $R_{\varepsilon}$ requires them only to be within some range.
Toom’s theorem implies that no such $R^{\prime}$ is ergodic. ∎

####  5.1.2. Relaxation time: a measure of information loss

Some readers, computer scientists in particular, may want to know already now
what relevance can results on inifinite cellular automata have on have on the
possibilities of computation or information storage in finite systems. We will
try to answer this question here. To stay in the context of the Toom rule, let
us consider a (finite or infinite) two-dimensional space $\mathbf{C}$. With an
extension of the notation (5.1) to two dimensions (where ${\mathbf{s}}$ is now
the array $(s_{ij}:-n\leq i,j\leq n)$), for any fixed ${\mathbf{s}}$, let us
define the variation distance for $\mu$ and $\nu$ when the latter are
restricted to $\SS_{n}$:

$d^{n}(\mu,\nu)=\sum\mathopen{\\{}\,|\mu({\mathbf{s}})-\nu({\mathbf{s}})|:{\mathbf{s}}\in\SS_{n}\,\mathclose{\\}}.$

Of course, $0\leq d_{n}(\mu,\nu)\leq 2$. Distance 2 means that the two
measures have disjoint support. Consider a set of sites

$\mathbf{C}_{m}=\mathbb{Z}_{m}\times\mathbb{Z}_{m}$

where $m$ can be finite or infinite. Suppose that for some $m$, the local
transition matrix (for simplicity, with nearest-neighbor interaction) gives
rise to a mixing Markov process with Markov operator $P_{m}$. Let

$D^{n}_{m}(t)=\bigvee_{\mu,\nu}d^{n}_{m}(P_{m}^{t}\mu,P_{m}^{t}\nu).$

######  Remark 5.4.

It is easy to see that this is equal to

$\bigvee_{{\mathbf{r}},{\mathbf{s}}}d^{n}_{m}(P_{m}^{t}\nu_{{\mathbf{r}}},\nu_{{\mathbf{s}}})$

where $\nu_{{\mathbf{s}}}({\mathbf{s}})=1$, i.e. $\nu_{{\mathbf{s}}}$ is the
measure concentrated on configuration ${\mathbf{s}}$. ∎

Notice that $D^{n}_{m}(t)$ is monotonically decreasing in $t$ since

$d^{n}_{m}(P_{m}^{t+u}\nu,\mu_{m})=d^{n}_{m}(P_{m}^{t}(P_{m}^{u}\nu),\mu_{m}).$

$P_{m}$ is mixing if and only if for each ${\mathbf{s}},\nu$ we have
$P_{m}^{t}\nu({\mathbf{s}})\to\mu_{m}({\mathbf{s}})$. By the weak compactness
of the space of measures, this is equivalent to saying that

$\lim_{t}D^{n}_{m}(t)=0$

holds for all $n$. The mixing of $P_{m}$ implies that there is an integer
function

$r_{m}(n,\delta)$

with $D^{n}_{\infty}(t)<\delta$ for all $t\geq r_{m}(n,\delta)$. We will call
$r_{m}(n,\delta)$ the relaxation time . This is obviously an increasing
function of $n$ (defined only for $n\leq(m-1)/2$) and a decreasing function of
$\delta$. In the cases we are interested in, the order of magnitude of
$r_{m}(n,\delta)$ as a function of $n$ does not change fast with the change of
$\delta$: $r_{m}(n,0.1)$) is not much larger than $r_{m}(n,1.9)$. This means
that once $\mu_{m}$ is not separated well from any $P_{m}^{t}\nu$ it soon
becomes fairly close to all of them. Therefore we will generally consider
$\delta$ fixed.

####  5.1.3. Relaxation time as a function of space size

If $m<\infty$ then the medium is always mixing. Assume now that the medium is
also mixing for $m=\infty$: we try to understand the implications of this fact
for finite $m$. We have the following relation:

######  Lemma 5.5.

For all $n<(m-1)/2$, for all $\delta$ with $r_{\infty}(n,\delta)<(m-1)/2-n$ we
have

$r_{m}(n,\delta)\leq r_{\infty}(n,\delta).$

This means that if the medium is mixing for $m=\infty$ then increasing $m$ in
the case of $m<\infty$ does not increase the relaxation time significantly for
any fixed $n$: in each segment of length $n$ of any finite medium, information
is being lost at least as fast as in the infinite medium.

###### Proof.

Take $m,n,\delta$ satisfying the above conditions and let
$r=r_{\infty}(n,\delta)$. Due to the monotonicity of $D^{n}_{m}(t)$, it is
enough to prove that $D^{n}_{m}(r)\leq D^{n}_{\infty}(r)$. Take a measure
$\nu$ over configurations of $\mathbf{C}_{m}$, this will give rise to some
measure $\nu_{\infty}$ over configurations of period $m$ in
$\mathbf{C}_{\infty}$ in a natural way, where $\nu_{\infty}$ is such that for
all $n<(m-1)/2$ and all ${\mathbf{s}}\in\SS_{n}$ we have
$\nu_{\infty}({\mathbf{s}})=\nu({\mathbf{s}})$. Then, $r<(m-1)/2-n$ implies
$2n+1+2r<m$ and therefore via (5.2) we have

$P_{m}^{r}\nu({\mathbf{s}})=P_{\infty}^{r}\nu_{\infty}({\mathbf{s}}).$

∎

We found that mixing of $P_{\infty}$ implies a kind of uniform forgetfulness
in the sense that increasing the size $m$ of the space does not help
increasing the relaxation time beyond $r_{\infty}(n,\delta)$.

####  5.1.4. Forgetfulness: a variant of ergodicity

Non-ergodicity does not express quite adequately the losing of all information
about the initial configuration in case of cellular automata, where namely the
space-time is translation-symmetric (this was noticed by Charles Radin and
Andrei Toom).

Let $\xi_{0}$ be the configuration over the one-dimensional integer lattice
that is 0 in the even places and 1 in odd places, and $\xi_{1}$ that is 1 in
the even places and 0 in the odd places. Let $\mu_{i}$ be the measure
concentrated on $\xi_{i}$ and let $P$ be some linear operator obtained from a
transition function. Suppose that the measures $P^{n}\mu_{0}$ converge to some
measure $\nu_{0}$. Then the measures $P^{n}\mu_{1}$ converge to some measure
$\nu_{1}$. Even if $\nu_{1}$ is different from $\nu_{0}$ they differ only by a
translation in space. If the translations of $\nu_{0}$ are the only invariant
measures of $P$ then we would still say that in some sense, $P$ loses all
information about the initial configuration: we might say, it loses all
“local” information. Indeed, a cell has no way of knowing whether it has even
or odd coordinates.

We can say that $P$ is strongly not forgetful if it has two disjoint (weakly)
closed translation-invariant sets of measures. Our non-ergodic examples all
have this property.

###  5.2. Information storage and computation in various dimensions

Let us be given an arbitrary one-dimensional transition function Tr and the
integers $N,L$. We define the three-dimensional transition function
${\text{Tr\/}}^{\prime}$ as follows. The interaction neighborhood is
$H\times\\{-1,0,1\\}$ with the neighborhood $H$ defined in Subsection 5.1
above. The transition function ${\text{Tr\/}}^{\prime}$ says: in order to
obtain your state at time $t+1$, first apply the transition function $R$ in
each plane defined by fixing the third coordinate. Then, apply transition
function Tr on each line obtained by fixing the first and second coordinates.
(The papers [14] and [11] use a neighborhood instead of $H$ that makes some
proofs easier: the northern, south-eastern and south-western neighbors.)

For an integer $m$, we define the space
$\mathbf{C}=\mathbb{Z}_{N}\times\mathbb{Z}_{m}^{2}$. For a trajectory $\xi$ of
${\text{CA\/}}({\text{Tr\/}})$ on $\mathbb{Z}_{N}$, we define the trajectory
$\zeta$ of ${\text{CA\/}}({\text{Tr\/}}^{\prime})$ on $\mathbf{C}$ by

(5.3) $\zeta(i,j,n,t)=\xi(n,t).$

Thus, each cell of ${\text{CA\/}}({\text{Tr\/}})$ is repeated $m^{2}$ times,
on a whole “plane” (a torus for finite $m$) in $\mathbf{C}$.

Then it is proved in earlier work that there are constants
$\varepsilon_{0},c_{1},d_{1}>0$ such that the following holds. For all $N,L$,
and $m=c_{1}\log(NL)$, for any trajectory $\xi$ of
${\text{CA\/}}({\text{Tr\/}})$ over $\mathbb{Z}_{N}$, if the trajectory
$\zeta$ of ${\text{CA\/}}({\text{Tr\/}}^{\prime})$ is defined by (5.3) then
for any $\varepsilon<\varepsilon_{0}$, any trajectory $(\mu,\eta)$ of
${\text{CA\/}}_{\varepsilon}({\text{Tr\/}}^{\prime})$ such that
$\eta(\cdot,0)=\zeta(\cdot,0)$ we have for all $t$ in $[0,L]$ and all
$w\in\mathbf{C}$

$\mu\mathopen{\\{}\,\eta(w,t)\neq\zeta(w,t)\,\mathclose{\\}}\leq
d_{1}\varepsilon.$

This theorem says that in case of the medium
${\text{CA\/}}_{\varepsilon}({\text{Tr\/}}^{\prime})$ and the trajectories
$(\mu,\zeta)$, the probability of deviation can be uniformly bounded by
$d_{1}\varepsilon$. The trajectories $\eta$ encode (by (5.3)) an arbitrary
computation (e.g. a universal Turing machine), hence this theorem asserts the
possibility of reliable computation in three-dimensional space. The coding is
repetition $O(\log^{2}(NL))$ times, i.e. it depends on the size $N\cdot L$ of
the computation. The decoding is even simpler: if a plane of $\mathbf{C}$
represents a state $s$ of a cell of ${\text{CA\/}}({\text{Tr\/}})$ then each
cell in this plane will be in state $s$ with large probability. The simulation
occurs in “real time”.

The original proof of a slightly weaker version of this result used a sparsity
technique borrowed from [10]. In its current form, the theorem was proved in
[5] using an adaptation of the techniqe of [27].

Theorem 2.5 shows that one-dimensional noisy and strongly not forgetful
probability operators exist. The proof of that theorem seems to require almost
the whole complexity of the constructions of the present paper (though the
continuous-time case adds some additional nuisance to each part of the proof).
Once the basic structure (an amplifier, as asserted in Lemma 3.7) is in place,
the simulations in it support arbitrary computational actions and allow the
formulation of several other theorems.

The following theorem asserts the possibility of storing much more
information. For the finite version, recall the definition of
${\text{Visible\/}}(k,N)$ in (4.23).

######  Theorem 5.6 (FCA, 1-dim, storage, discrete time).

There is

  * •

a transition function ${\text{Tr\/}}^{\prime}$ with a statespace having a
field ${\text{F\/}}^{1}$;

  * •

a hierarchical code $\Psi$ with a shared field $({\text{F\/}}^{k})$ as in
(4.13) such that $|{\text{Visible\/}}(K(N),N)|=N$;

  * •

constants $d_{1},c_{2}>0$;

such that for $h_{2}(n)=n^{c_{2}/\log\log n}$, for all $\varepsilon>0$, $t>0$,
for any configuration $\varrho$ with states in $\SS.{\text{F\/}}^{1}$,
trajectory $\eta$ of ${\text{CA\/}}_{\varepsilon}({\text{Tr\/}}^{\prime})$
over $\mathbf{C}=\mathbb{Z}_{N}$ (for finite or infinite $N$) with initial
configuration $\Gamma(\varrho;\Psi)$, for all $y$ in
${\text{Visible\/}}(K(N),N)$, we have

$\mathop{\operator@font
Prob}\mathopen{\\{}\,\varrho(y)\neq\eta(X(y;\Psi),t).{\text{F\/}}^{1}\,\mathclose{\\}}<d_{1}\varepsilon+t\varepsilon^{h_{2}(N)}.$

The code can be chosen to have $X(y;\Psi)=y$.

The function $\varepsilon^{h_{2}(N)}$ shows the length of time for which a
space of size $N$ can hold information.

A fault-tolerant computation is the trajectory of some perturbed medium
${\text{CA\/}}_{\varepsilon}({\text{Tr\/}}^{\prime})$ simulating the
trajectory of an arbitrary deterministic medium. The simulated transition
function Tr is arbitrary, but we might as well choose it to be a fixed
universal cellular automaton. Then ${\text{CA\/}}({\text{Tr\/}}^{\prime})$ can
be called a “universal fault-tolerant cellular automaton”. The exact form of
the theorems formulating the possibility of reliable computation is somewhat
arbitrary. It may seem more natural if the input of the computation is not
given in the initial configuration but is being fed through some cell
throughout the time of the computation. There are several choices also
concerning simplicity, the tradeoffs of space- and time-redundancy, etc. These
theorems should be considered therefore as just illustrations of the possible
use of the amplifiers of Lemma 3.7.

The basic idea is to implement a large but finite computation of Univ by
choosing the “active level” $k$ mentioned above so large that during the
planned computation, it is unlikely that there will be any fault at all in the
work of medium $M_{k}$. If the computation involves $N$ cells and $L$ steps
then this means that we should have, say, $NL\varepsilon_{k}<1/3$. Theorem 5.8
realizes this idea. In it, there are still several choices: simpler encoding
at the price of larger space redundancy, or more complex encoding at the proce
of less space redundancy and more time redundancy.

To formulate the theorems exactly, let Tr be any deterministic transition
function with distinguished fields Input, Output in the standard alphabet. We
say that Tr has monotonic output if for all trajectories $\eta$ of
${\text{CA\/}}({\text{Tr\/}})$ we have

$\eta(x,t).{\text{Output\/}}\preceq\eta(x,t+1).{\text{Output\/}}.$

We call the transition function Tr, all of whose fields have even size (i.e.
they are in the standard alphabet) together with some distinguished fields
Input, Output, a standard computing transition function if it

  1. (a)

is a separable transition function as defined in 2.2.1;

  2. (b)

never changes Input;

  3. (c)

has monotonic output;

  4. (d)

never changes anything if one of the three arguments is vacant or if the
middle argument has all $\\#$’s in its input field, or if all three arguments
have $*$ in all their fields.

######  Remark 5.7.

The Input and Output fields here have nothing to do with the Inbuf and Outbuf
fields introduced in 2.2.1. These are input and output of a certain large-
scale computation, while Inbuf and Outbuf concern the step-for-step
interaction of a cell with its neighbors. ∎

Let $\SS$ be the set of states for Tr, and let
$\varrho\in(\SS.{\text{Input\/}})^{\mathbb{Z}}$ be an “input configuration”.
Then the configuration

(5.4) $\zeta={\text{Init\/}}(\varrho)$

with states in $\SS$, is constructed as follows.

  1. (a)

For all $x\in\mathbb{Z}$, $\zeta(x).{\text{Input\/}}=\varrho(x)$ and
$\zeta(x).{\text{Output\/}}$ is filled with $*$;

  2. (b)

For all $x\in\mathbb{Z}$, all other fields of $\zeta(x)$ are filled with $*$;

  3. (c)

For all $x\not\in\mathbb{Z}$, we have $\zeta(x)={\text{Vac\/}}$.

If $\varrho$ is a configuration in $\SS^{\mathbb{Z}}$ where ${\|\SS\|}$ is
even, i.e. elements of $\SS$ can be viewed as strings in the standard
alphabet, then we say that $\varrho$ is supported by interval $I$ if
$\varrho(x)=*\cdots*$ or vacant for all $x\not\in I$. The support of $\varrho$
is defined to be the smallest interval supporting $\varrho$ and containing 0.
Let

(5.5) ${\text{Supp\/}}(\varrho)$

be the support of $\varrho$. For a space-time configuration $\zeta$ of a
standard computing medium, let

(5.6) ${\text{Supp\/}}(\zeta,t)=\bigcup_{u\leq
t}{\text{Supp\/}}(\zeta(\cdot,u)).$

######  Theorem 5.8 (FCA, 1-dim, discrete time, known bounds).

Let Tr be a standard computing transition function. There is

  * •

a transition function ${\text{Tr\/}}^{\prime}$ with a statespace having a
field ${\text{Output\/}}^{1}$;

  * •

constants $d_{1},c_{0},c_{1}>0$;

  * •

a hierarchical code with a shared field defined by $\Psi$ as in (4.13)

such that for $h_{0}(t)=\log\log t+c_{0}$, $h_{1}(t)=t\cdot(c_{1}\log
t)^{5\log\log\log t}$, for all $\varepsilon,s,t>0$, for any trajectory $\zeta$
of Tr over $\mathbb{Z}$ with $\zeta(\cdot,0)$ of the form
${\text{Init\/}}(\varrho)$ (see (5.4)), satisfying
$2|{\text{Supp\/}}(\zeta,t)|\leq s$, for any finite $K\geq h_{0}(t)$ and
possibly infinite $N$ satisfying
${\text{Supp\/}}(\zeta,t)\subset{\text{Visible\/}}(K,N)$, for any trajectory
$\eta$ of ${\text{CA\/}}_{\varepsilon}({\text{Tr\/}}^{\prime})$ over
$\mathbf{C}=\mathbb{Z}_{N}$ with initial configuration
$\Gamma(\varrho;K,\Psi)$, for all $y\in{\text{Supp\/}}(\zeta,t)$, we have

$\mathop{\operator@font
Prob}\mathopen{\\{}\,\zeta(y,t).{\text{Output\/}}\not\preceq\eta(X(y;K,\Psi),h_{1}(t)).{\text{Output\/}}^{1}\,\mathclose{\\}}<d_{1}\varepsilon.$

The code can be chosen to have $X(y;K,\Psi)=y$ and
$|{\text{Visible\/}}(K,N)|=N$.

Thus, to find a computation result $\zeta(y,u)$ of
${\text{CA\/}}({\text{Tr\/}})$, from some input, we must do the following.
Find a bound $s$ on $2|{\text{Supp\/}}(\zeta,t)|$ (the amount of space
required by the computation if we put the origin somewhere into the input),
then the level $K\geq h_{0}(t)$ on which the trajectory $\eta$ of the fault-
tolerant automaton ${\text{CA\/}}_{\varepsilon}({\text{Tr\/}}^{\prime})$
carries out the computation to the desired stage $u$ with the desired
reliability until step $t$. Embed the input into a configuration $\varrho$
whose support contains 0. Encode $\varrho$ into an initial configuration
$\Gamma(\zeta(\cdot,0);K)$ in a space whose size $N$ is large enough to have
${\text{Supp\/}}(\zeta,t)\subset{\text{Visible\/}}(K,N)$. “Run” the trajectory
$\eta$ until time $h_{1}(t)$, (it will be programmed to keep the active level
at $K$), and finally look up the result in site $X(y;K)$. Due to monotonic
output, it is always possible to look up the result later. If you look at it
too early the worst thing that can happen is that it will still be undefined.

The function $h_{1}(t)/t$ measures time redundancy while $X(y;h_{0}(t))/y$
measures space redundancy (which, as the theorem says, can be made constant).

The above theorem strengthens the result of [10] by eliminating the need for
the decoding of the computation result: we just have to look in the right
place for it. In two dimensions such a construction was given in [11]. The
time redundancy in that paper is $O(\log^{2+\delta}(NL))$ where $N,L$ are the
upper bounds on the space and time requirements of the computation. We believe
that this two-dimensional time redundancy can be reduced to
$\log^{1+\delta}(NL)$.

####  5.2.1. Adaptive encoding

Theorem 5.8 is not entirely satisfactory since its initial encoding (the
active level) depends on the knowledge of a time and space bound on the whole
computation. It is possible to remove this limitation. Instead of formulating
the theorem, we just describe the idea of the construction. The initial
encoding populates the space with cells of $M_{k}$ for all $k<K(N)$ where $N$
is the space size. Chose a level $k_{1}$ of encoding for the computation input
depending only on the size of the input. For an appropriately chosen
(universal) increasing sequence $({L}_{k})$, after ${L}_{k}$ computation steps
have been simulated, the active level will be raised from $k$ to $k+1$. The
parameters $k_{1}$ and $({L}_{k})$ are chosen to guarantee with high
probability that none of level $k$ cells involved in the actual computation
will fail before the level will be raised to $k+1$.

####  5.2.2. Self-organization

In the just-discussed hierarchical fault-tolerant computations, the initial
configuration is highly non-uniform since it encodes the hierarchy of
simulations described above. If we forgo this initialization then the
hierarchy must apparently be built up spontaneously. Initially, all sites in
the media $M_{2},M_{3},\ldots$ could be vacant but cells could emerge
spontaneously, as lower-level cells organize themselves (with the help of some
randomness) into colonies simulating higher-level cells. We call this feature
_self-organization_ , but postpone its formal definition a few sections later.

##  6\. Media

An abstract medium has been defined in 3.3 as essentially a set of stochastic
processes called its trajectories. Let us narrow this category somewhat. The
kind of abstract medium considered in this paper will simply be called a
medium. We will also restrict the kind of simulations among media to mappings
that by their very form will obviously be simulations: they will be called
canonical simulations.

###  6.1. Trajectories

Here, we will show in what form the set of trajectories of a medium will be
given.

####  6.1.1. Weak trajectories

In defining the conditions making up a medium we will make use of inequalities
of the form

$\mathbf{E}{g}\leq b$

where ${g}$ is an event function (as defined in Subsection 2.3), measurable in
$\mathcal{A}(V)$ for some rectangle $V$.

######  Example 6.1.

Let $V=[a_{1}+,a_{2}]\times[t+,u]$, $B<d=0.2(a_{2}-a_{1})$. Suppose that we
are given some ${\mathbf{r}}\in\SS^{3}$, $s\in\SS$. Let ${g}=1$ if there is a
space-time point $(x,t_{0})$ in $V$, and an $\varepsilon<d$ such that
$\eta(x+iB,t)=r_{i}$ for $i=-1,0,1$ during $[t_{0}-\varepsilon,t_{0}-]$ and
$\eta(x,t_{0})=s$. Thus, the event ${g}=1$ marks a certain kind of transition
in the window. ∎

A medium will be given by many such conditions. Let us fix an arbitrary
countable set $\mathbb{T}$ which will be called the set of condition types. A
medium is given as

(6.1) $M={\text{Med\/}}(\SS,\mathbf{C},{g}(\cdot,\cdot,\cdot),{b}(\cdot)).$

Here, $\SS$ is the set of possible local states and $\mathbf{C}$ is the set of
possible cell sites. The space $\mathbf{C}$ can also be omitted whenever it is
clear from the context. For all types $\alpha\in\mathbb{T}$ and rational
rectangles $V$, the medium assigns an event function

${g}(\alpha,V,\eta)$

and a bound ${b}(\alpha)\in[0,1]$. (We do not insist that
${g}(\alpha,V,\cdot)$ be measurable in $\mathcal{A}(V)$ though usually this
will be the case.) Therefore from now on, a local condition will be defined as
a pair

$(\alpha,V).$

The set $\SS$ is determined by $g$ implicitly. Also, generally local
conditions will only be defined for small $V$, and in a translation-invariant
way (in space, but only almost so in time since the time 0 is distinguished).
Therefore one and the same pair $g,b$ can serve for all sufficiently large
finite spaces $\mathbf{C}$ as well as the infinite space, just like with
deterministic cellular automata, where the same transition function determines
trajectories in finite spaces as well as the infinite space.

When we are given media $M_{1},M_{2},\ldots$ then ${g}_{i}(),{b}_{i}()$
automatically refer to $M_{i}$.

Two local conditions are disjoint when their rectangles are. A random space-
time configuration $\eta$ will be called a weak trajectory if for each time
$u\geq 0$, for each set of disjoint local conditions

$(\alpha_{i},V_{i})_{i\leq N}$

with $\min_{i}\mathbf{\pi}_{\text{t}}V_{i}\geq u$, if $h$ is an event function
over $\mathcal{A}_{u}$ then

(6.2)
$\mathbf{E}(h\prod_{i}{g}(\alpha_{i},V_{i},\eta))\leq\mathbf{E}h\prod_{i}{b}(\alpha_{i}).$

This says that we can multiply the probabilities of violating local conditions
in disjoint windows, i.e. that these violations happen “independently”.

####  6.1.2. Trajectories

The media we are going to be interested in have these three types of
condition.

  1. (1)

One type recognizes in $V$ a certain kind of value called “damage”, and has
$b=\varepsilon$ for some small $\varepsilon$;

  2. (2)

One type recognizes if there is no damage in $V$ and the transition does not
occur according to a certain transition function. This has $b=0$.

  3. (3)

One type corresponds to some “coin tossing” event, and has
$b=0.5+\varepsilon^{\prime}$ for a suitable $\varepsilon^{\prime}$.

If we need coin-tossing (we need it only for the results on self-organization)
then we must also consider certain sets of conditions that are chosen
randomly. A random local condition is a (measurable) function
$(\alpha,V(\eta))$ assigning a local condition to each space-time
configuration $\eta$. We recall the definition of stopping times from the
theory of stochastic processes, specialized to our present needs. A real
random variable $\sigma$ with values in $[0,\infty-]$ is a stopping time
derived from $\eta$ if for each $t$ the event $\sigma\leq t$ is in
$\mathcal{A}_{t}$. Let $\mathcal{A}_{\sigma}$ be the algebra of events $A$
with the property that $A\cap\\{\sigma\leq t\\}\in\mathcal{A}_{t}$. Assume
that for each $t$ in $[0,\infty-]$ there is random variable $V^{t}(\eta)$
measurable in $\mathcal{A}_{t}$ with values that are rational rectangles with

$\mathbf{\pi}_{\text{t}}V^{t}(\eta)\subset[t,\infty]$

and such that with probability 1 the function $V^{t}(\eta)$ is right semi-
continuous in $t$. This will be called a rectangle process derived from
$\eta$. We mention the following well-known fact from the theory or stochastic
processes:

######  Theorem 6.2 (see [21]).

$V^{\sigma}$ is a random variable measurable in $\mathcal{A}_{\sigma}$.

We will omit the words “derived from $\eta$” when they are clear from the
context. A random-stopping local condition is given by a triple

(6.3) $(\alpha,V^{t}(\eta),\sigma)$

where $\alpha$ is a type, $V^{t}(\eta)$ is a rectangle process and $\sigma$ is
a stopping time, both derived from $\eta$. This condition is supposed to
express the bound

$\mathbf{E}{g}(\alpha,V^{\sigma},\eta)\leq{b}(\alpha).$

For some finite set $N$ of indices, let us now be given a sequence

(6.4) $(\alpha_{i},V_{i}^{t},\sigma_{i})_{i\in N}$

of random-stopping local conditions. It is is called a system of disjoint
random local conditions if (for almost all $\eta$) all the rectangles
$V_{i}^{\sigma_{i}}(\eta)$ are disjoint, and there is a constant upper bound
on the $\sigma_{i}$ and a constant segment containing all
$\mathbf{\pi}_{\text{s}}V_{i}^{t}$. A random space-time configuration $\eta$
will be called a trajectory if for each set of disjoint random local
conditions as in (6.4) with $\sigma_{i}\geq u$, if $h$ is an event function
over $\mathcal{A}_{u}$ then

(6.5)
$\mathbf{E}(h\prod_{i}\bar{g}(i,\eta))\leq\mathbf{E}h\prod_{i}{b}(\alpha_{i})$

where

(6.6)
$\bar{g}(i,\eta)={g}{\bigl{(}\,\alpha_{i},V^{\sigma_{i}(\eta)}(\eta),\eta\,\bigr{)}}.$

This also says that we can multiply the probabilities of violating local
conditions in disjoint windows, but requires that this be even true if the
windows are chosen by random stopping rules.

Figure 9. A system of disjoint random local conditions

####  6.1.3. Examples of simple media

######  Example 6.3.

The first example will show how a PCA fits into this framework. Let us be
given a probabilistic cellular automaton ${\text{PCA\/}}(\mathbf{P},B,T)$. For
each state vector ${\mathbf{r}}\in\SS^{3}$ and state $s$, let us form type
$\alpha(s,{\mathbf{r}})$.This condition type says that the transition rules
are obeyed at times of the form $nT$. Then for cell $x$, time $t$ of the form
$nT$ with $n>0$, let

(6.7)
$\displaystyle{g}{\bigl{(}\,\alpha(s,{\mathbf{r}}),\;\\{x\\}\times[t-T+,t],\;\eta\,\bigr{)}}$
$\displaystyle=\\{\eta(x+iB,t-T)=r_{i}\;(i=-1,0,1),\;\eta(x,t)=s\\},$
$\displaystyle{b}(\alpha(s,r))$ $\displaystyle=\mathbf{P}(s,{\mathbf{r}}).$

For all cells $x$ and rational times $u$ we define some new type
$\beta=\beta(x,u)$by ${b}(\beta(x,u))=0$ and

${g}{\bigl{(}\,\beta(x,u),\;\\{(x,u)\\},\;\eta\,\bigr{)}}=\mathopen{\\{}\,\eta(x,u)\neq\eta(x,T{\lfloor
u/T\rfloor})\,\mathclose{\\}}.$

This condition says that $\eta(x,u)=\eta(x,T{\lfloor u/T\rfloor})$ with
probability 1\. For all other combinations $\alpha,V$ we set
${g}(\alpha,V,\eta)=0$. It is easy to see that the trajectories of
${\text{PCA\/}}(\mathbf{P},B,T)$ are trajectories of the medium defined this
way. ∎

######  Example 6.4.

The new conditions introduced below are “loosened-up” versions of the above
ones since it is not always desirable to be as restrictive. Let us be given a
probabilistic cellular automaton ${\text{PCA\/}}(\mathbf{P},B,T)$. For each
set of states $E$, and state vector ${\mathbf{r}}=(r_{-1},r_{0},r_{1})$ let

$\mathbf{P}(E,{\mathbf{r}})=\sum_{q\in E}\mathbf{P}(q,{\mathbf{r}}).$

Let $\mathbf{K}$ be the set of functions $K:\SS^{3}\to 2^{\SS}$ such that

(6.8) $K({\mathbf{r}})\subset\mathopen{\\{}\,s\neq
r_{0}:\mathbf{P}(s,{\mathbf{r}})>0\,\mathclose{\\}}.$

For a space-time trajectory $\eta$ and a $K\in\mathbf{K}$ let us write

$\overline{K}(x,t,\eta)=K(\eta(x-B,t),\eta(x,t),\eta(x+iB,t)).$

For all $K^{\prime},K^{\prime\prime}\in\mathbf{K}$ with $K^{\prime}\supset
K^{\prime\prime}$ (i.e. $K^{\prime}({\mathbf{r}})\supset
K^{\prime\prime}({\mathbf{r}})$ for all ${\mathbf{r}}$), let

$c(K^{\prime},K^{\prime\prime})=\bigvee_{{\mathbf{r}}}\frac{\mathbf{P}(K^{\prime\prime}({\mathbf{r}}),{\mathbf{r}})}{\mathbf{P}(K^{\prime}({\mathbf{r}}),{\mathbf{r}})}$

be the least upper bound, over ${\mathbf{r}}$, on the conditional probability
of getting into the set $K^{\prime\prime}({\mathbf{r}})$ provided we get into
the set $K^{\prime\prime}({\mathbf{r}})$. For each pair of such functions
$K^{\prime}\supset K^{\prime\prime}$ let us form the type

$\alpha=\alpha(K^{\prime},K^{\prime\prime}).$

For each cell $x$ and $u\leq v$ of the form $nT$, let us form the rectangle
$V=\\{x\\}\times[u+,v]$. For each such pair $\alpha,V$ let
${g}(\alpha,V,\eta)=1$ if there is a first $t\in[u+,v]$ with $\eta(x,t)\in
K^{\prime}(x,t-T,\eta)$ and in it, we have $\eta(x,t)\in
K^{\prime\prime}(x,t-T,\eta)$. Also, let
${b}(\alpha)=c(K^{\prime},K^{\prime\prime})$. ∎

######  Proposition 6.5.

If $M$ is the medium defined by the conditions above then
${\text{PCA\/}}(\mathbf{P},B,T)\subset M$.

###### Proof sketch.

The statement follows by a standard argument from the strong Markov property
of the Markov process ${\text{PCA\/}}(\mathbf{B},B,T)$ (see [21]). ∎

######  Example 6.6.

Consider a continuous-time cellular automaton ${\text{CCA\/}}(\mathbf{R},B)$.
For any functions $K,K^{\prime},K^{\prime\prime}\in\mathbf{K}$ as in Example
6.4, let

$\displaystyle\mathbf{R}(K,{\mathbf{r}})$ $\displaystyle=\sum_{q\in
K}\mathbf{R}(q,{\mathbf{r}}),$ $\displaystyle c(K^{\prime},K^{\prime\prime})$
$\displaystyle=\bigvee_{{\mathbf{r}}}\frac{\mathbf{R}(K^{\prime\prime}({\mathbf{r}}),{\mathbf{r}})}{\mathbf{R}(K^{\prime}({\mathbf{r}}),{\mathbf{r}})}.$

We define each $\alpha(K^{\prime},K^{\prime\prime})$, $V=\\{x\\}\times[u+,v]$
and ${g}(\alpha,V,\eta)$ as before, but now for all rational $u<v$. ∎

######  Theorem 6.7.

Every trajectory of ${\text{CCA\/}}(\mathbf{R},B)$ is a trajectory of the
medium defined in the above example.

###### Proof sketch.

As in 2.4.1, for a small $\delta>0$, let
$M_{\delta}={\text{PCA\/}}(\mathbf{P},B,\delta)$ with
$\mathbf{P}(s,{\mathbf{r}})=\delta\mathbf{R}(s,{\mathbf{r}})$ when $s\neq
r_{0}$ and $1-\delta\sum_{s^{\prime}\neq
r_{0}}\mathbf{R}(s^{\prime},{\mathbf{r}})$ otherwise. Then a transition to the
limit $\delta\to 0$ in Proposition 6.5 completes the proof. The transition
uses the fact that trajectories of $M(\delta)$ converge in distribution to
trajectories of ${\text{CCA\/}}(\mathbf{R},B)$. ∎

######  Remark 6.8.

Of course in both Proposition 6.5 and in Theorem 6.7, instead of the first
time with $\eta$ switching into $K^{\prime}$ we could have asked about the
second time, or the third time, etc. ∎

###  6.2. Canonical simulations

####  6.2.1. Definition of canonical simulations

Let us introduce a special kind of simulation, that establishes certain
relations between the local conditions of the media and thus makes it easier
to prove it is a simulation. Let $M_{1},M_{2}$ be media and let $\varphi^{*}$
be a mapping from the space-time configurations of $M_{1}$ into the evolutions
of $M_{2}$: we will write $\eta^{*}=\varphi^{*}(\eta)$. We say that
$\varphi^{*}$ is the map for a canonical simulation if the following holds.
Let $(\alpha,V)$ be any local condition for $M_{2}$. Then there is a system of
random local conditions

(6.9)
${\bigl{(}\,\beta(\alpha,i,j),W^{t}(\alpha,i,j,V,\eta),\tau(\alpha,i,j,V,\eta)\,\bigr{)}}$

with $i=1,\ldots,n(\alpha)$, $j=1,\ldots,k(\alpha,i)$,

(6.10) $\inf\mathbf{\pi}_{\text{t}}V\leq\tau(\alpha,i,j,V,\eta),$

such that for each fixed $i$, the subsystem containing elements for that $i$
forms a system of disjoint random local conditions with
$W^{t}(\alpha,i,j,V,\eta)\subset V$, and, defining

(6.11) $\displaystyle\bar{W}(\alpha,i,j,V,\eta)$
$\displaystyle=W^{\tau(\alpha,i,j,V,\eta)}(\alpha,i,j,V,\eta),$
$\displaystyle\bar{g}_{1}(\alpha,i,j,V,\eta)$
$\displaystyle={g}_{1}(\beta(\alpha,i,j),\bar{W}(\alpha,i,j,V,\eta),\eta),$

we have

(6.12) $\displaystyle{g}_{2}(\alpha,V,\eta^{*})$
$\displaystyle\leq\sum_{i}\prod_{j}\bar{g}_{1}(\alpha,i,j,V,\eta),$
$\displaystyle{b}_{2}(\alpha)$
$\displaystyle\geq\sum_{i}\prod_{j}{b}_{1}(\beta(\alpha,i,j)).$

A simulation map will be called a deterministic canonical simulation when the
system in (6.9) is deterministic: neither $\tau(\alpha,i,j,V,\eta)$ nor
$W^{t}(\alpha,i,j,V,\eta)$ depends on $\eta$. Under the condition mentioned in
the definition of weak trajectories (see (6.2)), we will be able to provide
deterministic canonical simulations and this is why weak trajectories are
sufficient. Canonical simulations are “cooked up” to make the following
theorem true.

######  Theorem 6.9 (Canonical Simulation).

If $\varphi^{*}$ is a canonical simulation map then for each trajectory $\eta$
of $M_{1}$, the expression $\varphi^{*}(\eta)$ defines a trajectory of
$M_{2}$.

###### Proof.

Let $\eta$ be a trajectory of $M_{1}$ and
$(\alpha_{l},V_{l}^{t},\sigma_{l})_{l\in N}$ a system of disjoint random local
conditions in $M_{2}$. Let $u$ be some time such that $\sigma_{l}\geq u$ for
each $l$, and let $h$ be an event function measurable in $\mathcal{A}_{u}$. We
must show

$\mathbf{E}{\bigl{(}\,h\prod_{l}\bar{g}_{2}(l,\eta^{*})\,\bigr{)}}\leq\mathbf{E}h\prod_{l}{b}_{2}(\alpha_{l}),$

where $\bar{g}_{2}(l,\zeta)$ is defined as in (6.6). By the assumption, for
each $l,V$ there is a system of disjoint random local conditions

${\bigl{(}\,\beta(\alpha_{l},i,j),W^{t}(\alpha_{l},i,j,V,\eta),\tau(\alpha_{l},i,j,V,\eta)\,\bigr{)}}$

for $i=1,\ldots,n(\alpha_{l})$ $j=1,\ldots,k(\alpha_{l},i)$ with the
properties defined for canonical simulations. Since $V$ has a countable range,
we obtain measurable functions even if we substitute
$V_{l}^{\sigma_{l}}(\eta^{*})$ into $V$ here. Let

$\bar{V}_{l}=V_{l}^{\sigma_{l}}(\eta^{*})$

and recall (6.11).

$\bar{\bar{W}}^{t}=\bar{W}^{t}(\alpha_{l},i,j,\bar{V}_{l},\eta)$ is a
rectangle process and $\tau(\alpha_{l},i,j,\bar{V}_{l},\eta)$ is a stopping
time.

Proof. It is easy to see that
$\mathbf{\pi}_{\text{t}}\bar{\bar{W}}^{t}\subset[t,\infty]$ and that the
process $\bar{\bar{W}}^{t}$ is upper semicontinuous almost everywhere. Let us
show that for each $t$ it is measurable in $\mathcal{A}_{t}$. We write

$\bar{W}^{t}(\alpha_{l},i,j,\bar{V}_{l},\eta)=W\Leftrightarrow\bigvee_{V}{\bigl{(}\,\bar{W}^{t}(\alpha_{l},i,j,V,\eta)=W\wedge
V=\bar{V}_{l}\,\bigr{)}}.$

Now (6.10) and $\tau(\alpha_{l},i,j,V,\eta)\leq t$ implies
$\inf\mathbf{\pi}_{\text{t}}V\leq t$. On the other hand by the definition of
random-stopping local conditions, $V=\bar{V}_{l}(=V_{l}^{\sigma_{l}})$ implies
$\sigma_{l}\leq\inf\mathbf{\pi}_{\text{t}}V$. Hence we can write the above
expression as

$\bigvee_{V}{\bigl{(}\,\bar{W}^{t}(\alpha_{l},i,j,V,\eta)=W\wedge
V=V_{l}^{\sigma_{l}}\,\bigr{)}}\wedge\sigma_{l}\leq t.$

By Theorem 6.2,

(6.13) $\bigl{\\{}\,\sigma_{l}\leq t\wedge
V=V_{l}^{\sigma_{l}}\,\bigr{\\}}\in\mathcal{A}_{t}.$

By the definition of the rectangle process $W^{t}$, also

$\bigl{\\{}\,\bar{W}^{t}(\alpha_{l},i,j,V,\eta)=W\,\bigr{\\}}\in\mathcal{A}_{t},$

hence indeed
$\mathopen{\\{}\,\bar{\bar{W}}^{t}=W\,\mathclose{\\}}\in\mathcal{A}_{t}$.
Finally, we have to show

$\bigl{\\{}\,\tau(\alpha_{l},i,j,\bar{V}_{l},\eta)\leq
t\,\bigr{\\}}\in\mathcal{A}_{t}.$

As above,

$\tau(\alpha_{l},i,j,\bar{V}_{l},\eta)\leq
t\Leftrightarrow\bigvee_{V}{\bigl{(}\,\tau(\alpha_{l},i,j,V,\eta)\leq t\wedge
V=\bar{V}_{l}\,\bigr{)}}$

which again can be written as

$\bigvee_{V}{\bigl{(}\,\tau(\alpha_{l},i,j,V,\eta)\leq t\wedge
V=V_{l}^{\sigma_{l}}\,\bigr{)}}\wedge\sigma_{l}\leq t.$

We have $\bigl{\\{}\,\tau(\alpha_{l},i,j,V,\eta)\leq
t\,\bigr{\\}}\in\mathcal{A}_{t}$ since $\tau(\alpha_{l},i,j,V,\eta)$ is a
stopping time; combining this with (6.13) completes the proof.

By (6.12) we have

(6.14)
${g}_{2}(\alpha,\bar{V}_{l},\eta^{*})\leq\sum_{i}\prod_{j}{g}_{1}(\alpha_{l},i,j,\bar{V}_{l},\eta).$

and

$\prod_{l}{b}_{2}(\alpha_{l})\geq\prod_{l}\sum_{i}\prod_{j}{b}_{1}(\beta(\alpha_{l},i,j))=\sum_{i(\cdot)}\prod_{l,j}{b}_{1}(\beta(\alpha_{l},i(l),j))$

where the last sum is over all functions $i(\cdot)$ with
$i(l)\in[1,n(\alpha_{l})]$. Similarly, by (6.14)

${g}_{2}(\alpha,\bar{V}_{l},\eta^{*})\leq\sum_{i(\cdot)}\prod_{l,j}\bar{g}_{1}(\alpha_{l},i(l),j,\bar{V}_{l},\eta).$

Therefore it is sufficient to show

$\mathbf{E}{\bigl{(}\,h\prod_{l,j}\bar{g}_{1}(\alpha_{l},i(l),j,\bar{V}_{l},\eta)\,\bigr{)}}\leq\mathbf{E}h\prod_{l,j}{b}_{1}(\beta(\alpha_{l},i(l),j)).$

Let us fix a function $i(l)$. Recall that by (6.11),

$\bar{g}_{1}(\alpha,i,j,\bar{V}_{l},\eta)={g}_{1}(\beta(\alpha,i,j),\bar{W}(\alpha_{l},i,j,\bar{V}_{l},\eta),\eta).$

For any $l,i$, the rectangles $\bar{W}(\alpha_{l},i,j,\bar{V}_{l},\eta)$ are
all disjoint and belong to $\bar{V}_{l}$. Also the sets $\bar{V}_{l}$ are
disjoint, therefore all rectangles
$\bar{W}(\alpha_{l},i(l),j,\bar{V}_{l},\eta)$ are disjoint. Recall that also
by (6.11),

$\bar{W}(\alpha,i,j,\bar{V}_{l},\eta)=W^{\tau(\alpha,i,j,\bar{V}_{l},\eta)}(\alpha,i,j,\bar{V}_{l},\eta),$

therefore the system

${\bigl{(}\,\beta(\alpha_{l},i(l),j),\bar{W}(\alpha,i,j,\bar{V}_{l},\eta),\tau(\alpha,i,j,\bar{V}_{l},\eta)\,\bigr{)}}$

taken for all $l,j$, is a system of disjoint random local conditions with
$u\leq\tau(\alpha,i,j,\bar{V}_{l},\eta)$, and hence the proof is finished by
the trajectory property of $\eta$. ∎

####  6.2.2. Frequency of switching times

Adding certain conditions does not really change some media. Let us call a
canonical simulation injective if the mapping $\varphi^{*}$ is the identity,
and the functions ${b}_{2}(\alpha),{g}_{2}(\alpha,\cdot,\cdot)$ differ from
${b}_{1},{g}_{1}$ only in that they are defined for some additional types
$\alpha$, too. Proving a certain probability bound for the behavior of
$\eta_{1}$ within some window does not create a canonical simulation yet: the
bound must be formulated in such a way that this type of probability bound can
be multiplied with itself and all the other bounds over a system of disjoint
windows (and these windows can even be chosen via stopping times).

Let us illustrate canonical simulations on the the following example. The
simulating medium $M_{1}$ is the CCA of Example 6.6. The conditions to add
impose lower and upper bounds on the frequency of switching times of $M_{1}$.
Namely, for some function $K\in\mathbf{K}$ let

$\displaystyle a_{-1}(K)$
$\displaystyle=\bigwedge_{{\mathbf{r}}}\mathbf{R}(K({\mathbf{r}}),{\mathbf{r}}),$
$\displaystyle a_{1}(K)$
$\displaystyle=\bigvee_{{\mathbf{r}}}\mathbf{R}(K({\mathbf{r}}),{\mathbf{r}}).$

Let us call a time $u$ of the space-time configuration $\eta$ a $K$-switching-
time of a cell $x$ if for all $t<u$ sufficiently close to $u$ we have
$\eta(x,u)\in K(x,t,\eta)$, i.e. we have just jumped into the target set
determined by $K(\cdot)$.

For some rational constant $D>0$, integers $l\geq 0$ and $j=-1,1$ let

(6.15)
${g}{\bigl{(}\,\alpha(K,D,k,j),\;\\{x\\}\times[u+,u+D],\;\eta\,\bigr{)}}$

be the event function of type $\alpha(K,D,k,j)$ for $j=-1$ [$j=1$] for the
event that site $x$ has at most [at least] $k$ times during $[u+,u+D]$, that
are $K$-switching times.

######  Proposition 6.10.

For each transition rate matrix $\mathbf{R}$ and function $K\in\mathbf{K}$
there is a function $\kappa(\varepsilon)>0$ such that for all $k>0$, defining,
with $a_{j}=a_{j}(K)$

$\displaystyle{b}(\alpha(K,D,(a_{j}+j\varepsilon)D,j))$
$\displaystyle=e^{-\kappa(\varepsilon)D}$ $\displaystyle\text{unless
}j=1\text{ and }(a_{1}+\varepsilon)D=1,$ (6.16)
$\displaystyle{b}(\alpha(K,D,1,1))$
$\displaystyle=e^{-\kappa(\varepsilon)D}\wedge a_{1}D$

(and defining ${b}(\alpha(K,D,k,j))=1$ for all other choices of $k$) the
trajectories of ${\text{CCA\/}}(\mathbf{R},B)$ are also trajectories of the
medium obtained by adding all these conditions.

The proof proceeds by first estimating the event in question by sums of
products of single switching events and using then a standard large-deviation
estimate.

###  6.3. Primitive variable-period media

We say that ${T_{\bullet}}>0$ is a dwell period lower bound of a space-time
configuration $\eta$ if no dwell period of $\eta$ is shorter than
${T_{\bullet}}$. A continuous-time cellular automaton has no such lower bound.

In the amplifier $M_{0},M_{1},\ldots$ we will construct eventually on top of a
continuous-time probabilistic cellular automaton $M_{0}$, all abstract media
$M_{1},M_{2},\ldots$ will have a dwell period lower bound, only $M_{0}$ will
not have one. $M_{1}$ will be a so-called primitive variable-period medium:
these can be considered the continuous-time extension of the notion of an
$\varepsilon$-perturbation of a deterministic cellular automaton with coin-
tossing. On the other hand, $M_{2},M_{3},\ldots$ will only fit into a more
general framework (non-adjacent cells).

Let us thus proceed to the definition of medium

${\text{Prim\\_var\/}}(\SS,\mathbf{C},{\text{Tr\/}},B,{T_{\bullet}},{T^{\bullet}},\varepsilon).$

The set $\SS$ of states is implicit in the transition function therefore from
now on, it will be omitted. We have dwell period lower and upper bounds
${T_{\bullet}}\leq{T^{\bullet}}$ and a failure probability bound
$\varepsilon>0$. The local state, as in Example 2.4, is a record with two
fields, Det and Rand where Rand consists of a single bit which is, say, always
the first bit.

To simplify the upper-bounding of dwell periods, we assume that the transition
function has the property

(6.17) ${\text{Tr\/}}(r_{-1},r_{0},r_{1}).{\text{Det\/}}\neq
r_{0}.{\text{Det\/}}.$

For a space-time configuration $\eta$, site $x$ and rational number $a>0$ let
$\sigma_{1}=\sigma_{1}(x,a,\eta)$, and $\sigma_{2}$ be the first and second
switching times $t>a$ of $\eta$ in $x$. Let us list the different types of
local condition.

  1. (a)

Conditions of type $\alpha({\text{dw\\_p\\_lb\/}})$ imposing ${T_{\bullet}}$
as a dwell period lower bound. We have
${b}(\alpha({\text{dw\\_p\\_lb\/}}))=\varepsilon$, and

${g}{\bigl{(}\,\alpha({\text{dw\\_p\\_lb\/}}),\;\\{x\\}\times[a,a+{T^{\bullet}}],\;\eta\,\bigr{)}}$

is the event function saying that $\eta(x,t)$ has two switching times closer
than ${T_{\bullet}}$ to each other during $[a+,a+{T_{\bullet}}-]$.

  2. (b)

Conditions of type $\alpha({\text{dw\\_p\\_ub\/}})$ imposing ${T^{\bullet}}$
as a dwell period upper bound. We have
${b}(\alpha({\text{dw\\_p\\_ub\/}}))=\varepsilon$, and

${g}{\bigl{(}\,\alpha({\text{dw\\_p\\_ub\/}}),\;\\{x\\}\times[a+,a+{T^{\bullet}}],\;\eta\,\bigr{)}}$

is the event function saying that $\eta(x,t)$ has no switching times in
$[a+,a+{T^{\bullet}}]$.

  3. (c)

Conditions of type $\alpha({\text{comput\/}})$ saying that the new value of
the Det field at a switching time obeys the transition function. We have
${b}(\alpha({\text{comput\/}}))=\varepsilon$, and

${g}{\bigl{(}\,\alpha({\text{comput\/}}),\;\\{x\\}\times[a,a+2{T^{\bullet}}],\;\eta\,\bigr{)}}\\\
=\\{\eta(x,\sigma_{2}).{\text{Det\/}}\not\in\mathopen{\\{}\,\overline{{\text{Tr\/}}}(\eta,x,t,B).{\text{Det\/}}:t\in[\sigma_{1},\sigma_{2}-{T_{\bullet}}/2]\,\mathclose{\\}}\\}.$

Here we used the notation (3.2).

  4. (d)

Conditions of type $\alpha({\text{coin\/}},j)$ for $j=0,1$ saying that the new
value of the Rand field at a switching time is obtained nearly by a fresh
coin-toss:

$\displaystyle{b}(\alpha({\text{coin\/}},j))$ $\displaystyle=0.5+\varepsilon,$
$\displaystyle{g}{\bigl{(}\,\alpha({\text{coin\/}},j),\;\\{x\\}\times[a,a+{T^{\bullet}}],\;\eta\,\bigr{)}}$
$\displaystyle=\\{\eta(x,\sigma_{2}).{\text{Rand\/}}=j\\}.$

Condition (c) says that unless an exceptional event occurred, whenever a state
transition takes place at the end of a dwell period $[\sigma_{1},\sigma_{2}]$
it occurs according to a transition made on the basis of the states of the
three neighbor cells and the random bit at some time in the observation
interval $[\sigma_{1},\sigma_{2}-{T_{\bullet}}/2]$. Since the observation
interval does not include the times too close to $\sigma_{2}$, information
cannot propagate arbitrarily fast.

######  Example 6.11.

All trajectories of the ordinary deterministic cellular automaton
${\text{CA\/}}({\text{Tr\/}},B,T)$ are also trajectories of
${\text{Prim\\_var\/}}({\text{Tr\/}},B,T,T,0)$. ∎

######  Theorem 6.12 (Simulation by CCA).

For medium

$M={\text{Prim\\_var\/}}({\text{Tr\/}},1,{T_{\bullet}},1,\varepsilon)$

with (6.17) and ${T_{\bullet}}<1$ there is a noisy transition rate
$\mathbf{R}(s,{\mathbf{r}})$ over some state space $\SS^{\prime}$ and a
function $\pi:\SS^{\prime}\to\SS$ such that $\pi(\eta(x,t))$ is a trajectory
of $M$ for each trajectory $\eta$ of ${\text{CCA\/}}(\mathbf{R},1)$.

The proof is a straightforward application of Proposition 6.10.

###  6.4. Main theorems (continuous time)

The first publication showing the possibility of reliable computation with a
continuous-time medium (in two dimenstions) is [30]. Here, we formulate the
new results for variable-period one-dimensional information storage and
computation. The following theorems are just like Theorems 2.5, 5.6 and 5.8
except that they have a variable-period medium
${\text{Prim\\_var\/}}({\text{Tr\/}}^{\prime},1,{T_{\bullet}},1,\varepsilon)$
with ${T_{\bullet}}=0.5$ in place of the perturbed discrete-time automaton
${\text{CA\/}}_{\varepsilon}({\text{Tr\/}}^{\prime})$. See the Corollary below
for continuous-time interacting particle systems.

######  Theorem 6.13 (1-dim non-ergodicity, variable-period).

There is a one-dimensional transition function such that its primitive
variable-period perturbations remember a field.

######  Theorem 6.14 (FCA, 1-dim, storage, variable-period).

There is

  * •

a transition function Tr;

  * •

a hierarchical code $\Psi$ with a shared field $({\text{F\/}}^{k})$ as in
(4.13);

  * •

constants $d_{1},c_{2}>0$;

such that for $h_{2}(n)=n^{c_{2}/\log\log n}$, all $\varepsilon>0$, $t>0$, for
${T_{\bullet}}=0.5$, any configuration $\varrho$ with states in
$\SS.{\text{F\/}}^{1}$, trajectory $\eta$ of
${\text{Prim\\_var\/}}({\text{Tr\/}},1,{T_{\bullet}},1,\varepsilon)$, over
$\mathbf{C}=\mathbb{Z}_{N}$ (for finite or infinite $N$) with initial
configuration $\Gamma(\varrho;\Psi)$, for all for all $y$ in
${\text{Visible\/}}(K(N),N)$, we have

$\mathop{\operator@font
Prob}\mathopen{\\{}\,\varrho(y)\neq\eta(X(y;\Psi),t).{\text{F\/}}^{1}\,\mathclose{\\}}<d_{1}\varepsilon+t\varepsilon^{h_{2}(N)}.$

The code can be chosen to have $X(y;K,\Psi)=y$.

The main result of the present paper is the following one, asserting the
existence of a one-dimensional fault-tolerant variable-period cellular
automaton:

######  Theorem 6.15 (FCA, 1-dim, variable period, known bounds).

This theorem says the same as Theorem 5.8, with again
${\text{Prim\\_var\/}}({\text{Tr\/}}^{\prime},1,0.5,1,\varepsilon)$, replacing
${\text{CA\/}}_{\varepsilon}({\text{Tr\/}}^{\prime})$.

For the interpretation of this theorem, see the comment after Theorem 5.8. The
construction indicated in 5.2.1 has a similar variable-period counterpart.
Theorem 6.12 implies the following.

######  Corollary 6.16 (Interacting particle system construction).

In Theorems 6.13, 6.14, 6.15, we can replace ${\text{Tr\/}}^{\prime}$ with a
rate matrix $\mathbf{R}$ and
${\text{Prim\\_var\/}}({\text{Tr\/}}^{\prime},1,{T_{\bullet}},1,\varepsilon)$,
with a CCA with rates coming from an arbitrary $\varepsilon$-perturbation of
$\mathbf{R}$. This proves, in particular, Theorem 2.6.

###  6.5. Self-organization

If the input information is a single symbol then an (infinite or large finite)
hierarchical initial configuration in the above reliable simulation theorems
is less natural than one consisting of the repetition of this symbol.

######  Theorem 6.17 (FCA, 1-dim, storage, variable-period, self-organizing).

For each $m$ there is

  * •

a transition function Tr with state space $\SS$ having a field Output;

  * •

a mapping $\gamma:\\{0,1\\}^{m}\to\SS$;

  * •

constants $c_{1},c_{2}>0$,

such that for $h_{2}(n)=n^{c_{2}/\log\log n}$, $\varepsilon>0$, $t>0$, for any
string $s$ of length $m$ in the standard alphabet, any trajectory $\eta$ of
${\text{Prim\\_var\/}}({\text{Tr\/}},1,{T_{\bullet}},1,\varepsilon)$ over
$\mathbf{C}=\mathbb{Z}_{N}$ (for finite or infinite $N$) having initial
configuration $\eta(y,0)=\gamma(s)$ for all $y$, the following holds for all
$x$:

$\mathop{\operator@font
Prob}\mathopen{\\{}\,s\neq\eta(x,t).{\text{Output\/}}\,\mathclose{\\}}/c_{1}<\varepsilon+t\varepsilon^{h_{2}(N)}+(t^{2}\varepsilon)\wedge(t^{-0.4}+N^{-0.4}).$

Though it is not seen from the theorem, hierarchical organization actually
emerges here: the configuration $\eta(\cdot,t)$ will consist of islands of
varying levels of “organization” and the level will be generally growing with
$t$. For infinite $N$ we can ignore the terms involving $N$ (since they
converge to 0), obtaining $\varepsilon+(t^{2}\varepsilon)\wedge t^{-0.4}$. The
term $t^{-0.4}$ decreases rather slowly. This term is essentially the upper
bound on the probability that organization does not grow to the required level
until time $t$.

To formulate a theorem about self-organizing computation, assume that the
input is again, as in the storage case, just a binary string $s$ fitting into
a single cell. (If you want a larger input, we would have to encode it into a
higher-order cell and repeat that cell.) However, the simulated computation
may last forever producing ever-growing monotonic output. Where to read the
currently available output when the input has no distinguished origin? This
must depend on the length of the output. We can expect that there is a
constant $c_{0}$ such that for some sequences of lengths
$B^{\prime}_{1}<B^{\prime}_{2}<\cdots$, $B_{1}<B_{2}<\cdots$, if the
computation output is a string of length $\geq B^{\prime}_{k}$ by some time
$t$, then by all times exceeding a certain time $h_{1}(t)$, its first segment
of length $B^{\prime}_{k}$ “can be located somewhere” in every interval
$I_{k}(x)=[x,x+c_{0}B_{k}]$. Since this requires the short starting segments
of the output to occur more densely than the longer ones, we store the output
on infinitely many different tracks simultaneously. As for the infinitely many
fields ${\text{F\/}}_{i}^{k}$ in Proposition 4.10, let $Y+X_{k}(y)$ denote the
position where the $y$-th symbol of the $k$-th track is stored, if the storage
starts at position $Y$. (In our construction, $Y$ will be the site of a cell
of the simulated medium $M_{k}$ whose body fits into $I_{k}(x)$.)

The theorem on self-organizing computation says that there is a constant
$d_{0}$ and a function $Y_{k}(\cdot,\cdot,\cdot)$ such that for every
$k,x,y,t$, in every interval $I_{k}(x)$, with $Y=Y_{k}(x,h_{1}(t),\eta)$, with
probability $\geq 1-d_{0}\varepsilon$ we have

$\zeta(y,t).{\text{Output\/}}\preceq\eta(Y+X_{k}(y),h_{1}(t)).{\text{F\/}}_{1}^{1}.$

##  7\. Some simulations

###  7.1. Simulating a cellular automaton by a variable-period medium

The random nature of the switching times of a variable-period medium is a tame
kind of nondeterminism; any deterministic cellular automaton can be simulated
by a variable-period medium. To prove this we first introduce an auxiliary
concept. Let us define the totally asynchronous cellular automaton

${\text{ACA\/}}({\text{Tr\/}})={\text{ACA\/}}({\text{Tr\/}},1,1)$

associated with transition function Tr as follows: $\eta$ is a trajectory if
for all $x,t$ we have either $\eta(x,t+1)=\eta(x,t)$ or the usual

$\eta(x,t+1)={\text{Tr\/}}(\eta(x-1,t),\eta(x,t),\eta(x+1,t)).$

A site $x$ is free in a configuration $\xi$ if
${\text{Tr\/}}(\xi(x-1),\xi(x),\xi(x+1))\neq\xi(x)$. The set of free sites
will be denoted by $L(\xi)$. For a space configuration $\xi$ and a set $E$ of
sites, let us define the new configuration ${\text{Tr\/}}(\xi,E)$ by

${\text{Tr\/}}(\xi,E)(x)=\begin{cases}{\text{Tr\/}}(\xi(x-1),\xi(x),\xi(x+1))&\text{if
$x\in E$}\\\ \xi(x)&\text{otherwise.}\end{cases}$

Now we can express the condition that $\eta$ is a trajectory of
${\text{ACA\/}}({\text{Tr\/}})$ by saying that for every $t$ there is a set
$U$ with

(7.1) $\eta(\cdot,t+1)={\text{Tr\/}}(\eta(\cdot,t),U).$

Let the update set

(7.2) $U(t,\eta)$

be the set of sites $x$ with $\eta(x,t+1)\neq\eta(x,t)$. The initial
configuration and the update sets $U(t,\eta)$ determine $\eta$. For any set
$A$, let us use the indicator function

$\chi(x,A)=\begin{cases}1&\text{if $x\in A$,}\\\
0&\text{otherwise.}\end{cases}$

For given $\eta$ we define the function $\tau(x,t)=\tau(x,t,\eta)$ as follows:

(7.3) $\displaystyle\tau(x,0)$ $\displaystyle=0,$ $\displaystyle\tau(x,t+1)$
$\displaystyle=\tau(x,t)+\chi(x,U(t,\eta)).$

We can call $\tau(x,t)$ the effective age of $x$ in $\eta$ at time $t$: this
is the number of effective updatings that $x$ underwent until time $t$. Given
a transition function Tr and an initial configuration $\xi$, we say that the
function has invariant histories if there is a function
$\zeta(x,u)=\zeta(x,u,\xi)$ such that for all trajectories $\eta(x,t)$ of
${\text{ACA\/}}({\text{Tr\/}})$ with $\eta(\cdot,0)=\xi$ we have

(7.4) $\eta(x,t)=\zeta(x,\tau(x,t,\eta),\xi).$

This means that after eliminating repetitions, the sequence
$\zeta(x,1),\zeta(x,2),\ldots$ of values that a site $x$ will go through
during some trajectory, does not depend on the update sets, only on the
initial configuration (except that the sequence may be finite if there is only
a finite number of successful updates). The update sets influence only the
delays in going through this sequence. Let

${\text{Tr\/}}(\xi,E,F)={\text{Tr\/}}({\text{Tr\/}}(\xi,E),F).$

We call a transition function Tr commutative if for all configurations $\xi$
and all distinct pairs $x,y\in L(\xi)$ we have
${\text{Tr\/}}(\xi,\\{x\\},\\{y\\})={\text{Tr\/}}(\xi,\\{y\\},\\{x\\})$. The
paper [12] proves the theorem that if a transition function is commutative
then it has invariant histories. In Theorem 7.1 below, we will give a simple
example of a universal commutative transition function. For that example, the
theorem can be proved much easier.

Below, we will use the smallest absolute-value remainders

(7.5) $b\mskip-4.0mu plus -2.0mu minus -4.0mu\mkern
5.0mu\mathbin{\operator@font amod}\penalty 900\mkern 5.0mu\mskip-4.0mu plus
-2.0mu minus -4.0mum$

with respect to a positive integer $m>2$, defined by the requirement
$-m/2<b\mskip-4.0mu plus -2.0mu minus -4.0mu\mkern
5.0mu\mathbin{\operator@font amod}\penalty 900\mkern 5.0mu\mskip-4.0mu plus
-2.0mu minus -4.0mum\leq m/2$.

######  Theorem 7.1 (Commutative Simulation).

Let ${\text{Tr\/}}_{2}$ be an arbitrary transition function with state space
$\SS_{2}$. Then there is a commutative transition function ${\text{Tr\/}}_{1}$
with state space $\SS_{1}=\SS_{2}\times R$ (for an appropriate finite set $R$)
with the following property. Each state $s\in\SS_{1}$ can be represented as
$(s.{\text{F\/}},s.{\text{G\/}})$ where $s.{\text{F\/}}\in\SS_{2}$,
$s.{\text{G\/}}\in R$. Let $\xi_{2}$ be an arbitrary configuration of
$\SS_{2}$ and let $\xi_{1}$ be a configuration of $\SS_{1}$ such that for all
$x$ we have $\xi_{1}(x).{\text{F\/}}=\xi_{2}(x)$,
$\xi_{1}(x).{\text{G\/}}=0\cdots 0\in R$. Then for the trajectory $\eta_{1}$
of ${\text{CA\/}}({\text{Tr\/}}_{1})$, with initial configuration $\xi_{1}$,
the function $\eta_{1}(x,t).{\text{F\/}}$ is a trajectory of
${\text{CA\/}}({\text{Tr\/}}_{2})$. Moreover, in $\eta_{1}$, the state of each
cell changes in each step.

In other words, the function ${\text{Tr\/}}_{1}$ behaves in its field F just
like the arbitrary transition function ${\text{Tr\/}}_{2}$, but it also
supports asynchronous updating.

###### Proof.

Let $U>2$ be a positive integer and

${\text{Cur\/}},{\text{Prev\/}},{\text{Age\/}}$

be three fields of the states of $\SS_{1}$, where
${\text{F\/}}={\text{Cur\/}}$,
${\text{G\/}}=({\text{Prev\/}},{\text{Age\/}})$. The field Age represents
numbers mod $U$. It will be used to keep track of the time of the simulated
cells mod $U$, while Prev holds the value of Cur for the previous value of
Age.

Let us define $s^{\prime}={\text{Tr\/}}_{1}(s_{-1},s_{0},s_{1})$. If there is
a $j\in\\{-1,1\\}$ such that
$(s_{j}.{\text{Age\/}}-s_{0}.{\text{Age\/}})\mskip-4.0mu plus -2.0mu minus
-4.0mu\mkern 5.0mu\mathbin{\operator@font amod}\penalty 900\mkern
5.0mu\mskip-4.0mu plus -2.0mu minus -4.0muU<0$ (i.e. some neighbor lags
behind) then $s^{\prime}=s_{0}$ i.e. there is no effect. Otherwise, let
$r_{0}=s_{0}.{\text{Cur\/}}$, and for $j=-1,1$, let $r_{j}$ be equal to
$s_{j}.{\text{Cur\/}}$ if $s_{j}.{\text{Age\/}}=s_{0}.{\text{Age\/}}$, and
$s_{j}.{\text{Prev\/}}$ otherwise.

$\displaystyle s^{\prime}.{\text{Cur\/}}$
$\displaystyle={\text{Tr\/}}_{2}(r_{-1},r_{0},r_{1}),$ $\displaystyle
s^{\prime}.{\text{Prev\/}}$ $\displaystyle=s_{0}.{\text{Cur\/}},$
$\displaystyle s^{\prime}.{\text{Age\/}}$
$\displaystyle=s_{0}.{\text{Age\/}}+1\bmod U.$

Thus, we use the Cur and Prev fields of the neighbors according to their
meaning and update the three fields according to their meaning. It is easy to
check that this transition function simulates ${\text{Tr\/}}_{2}$ in the Cur
field if we start it by putting 0 into all other fields.

Let us check that ${\text{Tr\/}}_{1}$ is commutative. If two neighbors $x,x+1$
are both allowed to update then neither of them is behind the other modulo
$U$, hence they both have the same Age field. Suppose that $x$ updates before
$x+1$. In this case, $x$ will use the Cur field of $x+1$ for updating and put
its own Cur field into Prev. Next, since now $x$ is “ahead” according to Age,
cell $x+1$ will use the Prev field of $x$ for updating: this was the Cur field
of $x$ before. Therefore the effect of consecutive updating is the same as
that of simultaneous updating.∎

The commutative medium of the above proof will be called the marching soldiers
scheme since its handling of the Age field reminds one of a chain of soldiers
marching ahead in which two neighbors do not want to be separated by more than
one step.

Figure 10. The Marching Soldiers scheme. The effective age of neighbor sites
differs by at most 1.

######  Remark 7.2.

In typical cases of asynchronous computation, there are more efficient ways to
build a commutative transition function than to store the whole previous state
in the Prev field. Indeed, the transition function typically has a bandwidth
(see 2.2.1) smaller than ${\|\SS\|}$. ∎

######  Corollary 7.3 (Variable-period simulation).

For every deterministic transition function ${\text{Tr\/}}_{2}$ over some
state-space $\SS_{2}$, there is a set of states $\SS_{1}$, a transition
function ${\text{Tr\/}}_{1}$
over $\SS_{1}$, and a code that for any values
${T_{\bullet}}_{1}\leq{T^{\bullet}}_{1}$, is a simulation of
${\text{CA\/}}({\text{Tr\/}}_{2})$ by
${\text{Prim\\_var\/}}({\text{Tr\/}}_{1},1,{T_{\bullet}}_{1},{T^{\bullet}}_{1},0)$.

###### Proof.

Let ${\text{Tr\/}}_{1}$ be the commutative transition function given by
Theorem 7.1, with the fields ${\text{F\/}},{\text{G\/}}$. Let $\xi_{2}$ be an
arbitrary configuration of $S_{2}$ and let $\xi_{1}$ be a configuration of
$S_{1}$ defined in the statement of the same theorem. Let $\eta_{1}$ be a
trajectory of
${\text{Prim\\_var\/}}({\text{Tr\/}}_{1},1,{T_{\bullet}}_{1},{T^{\bullet}}_{1},0)$,
with the starting configuration $\xi_{1}$.

An update set $U(t,\eta_{1})$ similar to (7.2) can be defined now for the
trajectory $\eta_{1}$ as follows: $x$ is in $U(t,\eta_{1})$ iff $t$ is a
switching time of $\eta_{1}$. Similarly, $\tau(x,t,\eta_{1})$ can be defined
as in (7.3):

$\displaystyle\tau(x,0)$ $\displaystyle=0,$ $\displaystyle\tau(x,t)$
$\displaystyle=\tau(x,t-)+\chi(x,U(t,\eta_{1})).$

With these, let us define

$\displaystyle\sigma(x,s,\xi)$
$\displaystyle=\bigwedge\mathopen{\\{}\,t:\tau(x,t,\eta^{\prime})=s\,\mathclose{\\}},$
$\displaystyle\eta_{2}(x,s,\xi)$
$\displaystyle=\eta_{1}(x,\sigma(x,s)).{\text{F\/}}$

By the cited theorem, $\eta_{2}$ is a trajectory of
${\text{CA\/}}({\text{Tr\/}}_{2})$.∎

The simulation in this theorem is not a local one in the sense defined in
Subsection 3.6 since it changes the time scale. For an analysis of such
simulations, see [5].

###  7.2. Functions defined by programs

Let us recall the definition of a standard computing transition function as
introduced in Subsection 5.2, and let us call a cellular automaton with such a
transition function a standard computing medium. For a standard computing
transition function Tr, integers $s$ and $t$ and string $X$ consider a
trajectory $\eta$ of ${\text{CA\/}}({\text{Tr\/}})$ over the rectangle
$[0,s]\times[0,t]$ with an initial configuration in which
$\eta(0,0)=\eta(s,0)=\\#\cdots\\#$, further $X$ is on the input track on
$[1,s-1]$ (padded with $*$’s to fill up $[1,s-1]$), $*$’s on the output track
and 0’s on the other tracks. This defines a trajectory $\eta$ since the
$\\#$’s on the input field in cells 0 and $s$ imply that the cells outside the
interval $[0,s]$ will have no effect.

Assume that at time $t$, the Output track has no $*$ on $[1,s-1]$. Then the
output never changes anymore (it is monotonic in standard computing media).
The string $w$ on the Output track on $[1,s-1]$ will be called the result of
the computation, denoted by

$w={\text{Tr\/}}(X;s,t).$

Figure 11. Definition of $\text{trans}(X;s,t)$

####  7.2.1. Efficient universality

We say that the standard computing transition function ${\text{Tr\/}}_{0}$ is
efficiently universal if for every standard computing transition function Tr,
there is a string prog and constant $c$ such that for all strings $X$ and
positive integers $s,t$ we have

${\text{Tr\/}}(X;s,t)={\text{Tr\/}}_{0}({\text{prog\/}}\sqcup X;cs,c(s+t))$

whenever the left-hand side is defined. In other words, ${\text{Tr\/}}_{0}$
can simulate the computation of any other standard computing transition Tr if
we prepend a “program of Tr”. The space and time needed for this simulation
can only be a constant factor greater than those of the simulated computation.

######  Theorem 7.4.

There are efficiently universal standard computing transition functions.

###### Sketch of the proof.

This theorem can be proven similarly to Theorem 3.5. The main addition to the
construction is that before ${\text{Tr\/}}_{0}$ starts a block simulation of
Tr the input will be distributed bit-by-bit to the colonies simulating the
cells of Tr. At the end, the output will be collected from these colonies.∎

We fix an efficiently universal standard computing transition function

(7.6) Univ

for the definition of various string functions. In view of Theorem 7.1, we can
(and will) also assume that Univ is commutative. For a string function $f(X)$
defined over some domain $E$ we will say that prog is a program for $f$ with
time complexity bound $t$ and space complexity bound $s$ over $E$ if we have

${\text{Univ\/}}({\text{prog\/}}\sqcup X;s,t)=f(X).$

It is often convenient to define a finite function (like a transition function
of some medium, or a code) by its program (for Univ) rather than its
transition table, since for many interesting functions, the program can be
given in a more concise form.

###  7.3. The rule language

This subsection defines a language for describing a transition function that
is more convenient than giving a complete transition table. A transition
function will generally be defined by a set of rules which impose some
conditions on it. In case some rules are contradictory and no precedence is
stated between them then rules given later override the ones given earlier.
Rules are sometimes associated with certain fields. The lowest-priority rule
referring to a field is called the default.

Some rules will not be applicable directly, but will rather be used by other
rules: these will be called subrules. A subrule R is just like other rule,
except that, typically, there is some other rule saying in which time interval
of the work period to invoke R.

Our use of the rule language will not be completely formal but it will be
evident how to make it formal. In a semi-formal description of a rule,
${\mathbf{x}}$ refers to the cell to which it is applied. This is only a
convenient shorthand that can be replaced with references to fields of the
cell and its neighbors. We will write

$\vartheta_{j}(x)=x+jB$

for the site $j$ steps from $x$. In the condition as well as the action of the
rule, a field ${\text{F\/}}({\mathbf{x}})$ will simply be written as F. We
will often write

${\text{F\/}}^{j}=\eta.{\text{F\/}}(\vartheta_{j}({\mathbf{x}})).$

For example, for field Addr, instead of writing “if
$\eta.{\text{Addr\/}}({\mathbf{x}})=0$ and
${\text{Addr\/}}(\vartheta_{j}({\mathbf{x}}))=1$” we will write “if
${\text{Addr\/}}=0$ and ${\text{Addr\/}}^{j}=1$”.

The simplest possible rule is an assignment of the form ${\text{F\/}}:=g$
where F is a field and $g$ is a function of some fields, e.g.
${\text{F\/}}:=G^{-1}+H^{1}$. Another possible rule is the conditional:

| cond {
---|---
? $C_{1}$
! $A_{1}$
$\ldots$
? $C_{k}$
! $A_{k}$
[?! $A_{k+1}$]
}

Here, $C_{1},C_{2},\ldots$ are conditions: inequalities and equations in terms
of the states of $\vartheta_{j}({\mathbf{x}})$, and $A_{1},\ldots,A_{k+1}$ are
possible actions each of which can be another rule. We can use logical
connectives, even (finite) quantifiers in the conditions. The above rule says
that if condition $C_{1}$ is satisfied then the action $A_{1}$ must be
performed. Else if $C_{2}$ holds then action $A_{2}$ must be performed, etc.
Finally, and optionally, (this is meant by “[,]”) if all conditions fail then
we may require a default action $A_{k+1}$ to be performed. The symbols ?, !,
?! abbreviate condition, action and default respectively. An alternative way
of writing would be

|  if $C_{1}$ {
---|---
then $A_{1}$
else if $C_{2}$
then $A_{2}$
$\ldots$
else $A_{k+1}$
}

######  Remark 7.5.

We prefer the first form (borrowed from the programming language LISP) only in
order to put all conditions formally on the same level. ∎

The rule

${\text{R\/}}_{1}\hbox{$\mskip 4.0mu plus 2.0mu minus 4.0mu\parallel\mskip
4.0mu plus 2.0mu minus 4.0mu$}{\text{R\/}}_{2}$

is a combination of two rules. It says that both rules must be carried out
simultaneously. In case the two rules are just two assignments we will
sometimes omit the sign $\mskip 4.0mu plus 2.0mu minus 4.0mu\parallel\mskip
4.0mu plus 2.0mu minus 4.0mu$. The rule

${\text{R\/}}_{1};{\text{R\/}}_{2}$

asks for carrying out the rules ${\text{R\/}}_{1}$ and ${\text{R\/}}_{2}$
consecutively. This informal notation can be understood in terms of a field
Age which we are always going to have and can be replaced with a conditional.
E.g., whenever we write

|  Retrieve;
---|---
Eval

then this can be replaced, using appropriate constants $t_{i}$, with

| cond {
---|---
? $t_{1}\leq{\text{Age\/}}<t_{2}$
! Retrieve
? $t_{2}\leq{\text{Age\/}}<t_{3}$
! Eval
}

We will also use the construct

for $i=a$ to $b$ ${\langle\text{ some rule referring to }i\rangle}$.
---

The construct

repeat $k$ times ${\langle\cdots\rangle}$
---

is a special case.

A subrule can have parameters (arguments). Subrule $P(i)$ with parameter $i$
can be viewed as a different rule for each possible value of $i$. An example
could be a simple subrule ${\text{Read\\_Mail\/}}(j)$ which for
$j\in\\{-1,1\\}$ has the form

${\text{Mail\/}}:={\text{Mail\/}}^{j}$

for the field Mail. We will also have functions: these are defined by the
information available in the arguments of the transition function, and can
always be considered a shorthand notation: e.g., we could denote

$f(i)={\text{Addr\/}}+{\text{Age\/}}^{i}.$

The construct

let $k=\ldots$
---

can be understood as notational shorthand (though could also be incorporated
into the rule language).

######  Example 7.6.

Here is a description of the transition function given in the proof of Theorem
7.1 (Asynchronous Simulation).

|  rule March {
---|---
for $j\in\\{-1,0,1\\}$, {
let $r(j)={\text{Cur\/}}^{j}$ if ${\text{Age\/}}^{j}={\text{Age\/}}$, and
${\text{Prev\/}}^{j}$ otherwise; }
cond {
? $\forall j\in\\{-1,1\\}$ $({\text{Age\/}}^{j}-{\text{Age\/}})\mskip-4.0mu
plus -2.0mu minus -4.0mu\mkern 5.0mu\mathbin{\operator@font amod}\penalty
900\mkern 5.0mu\mskip-4.0mu plus -2.0mu minus -4.0muU\geq 0$
! {
${\text{Prev\/}}:={\text{Cur\/}}$;
${\text{Cur\/}}:={\text{Tr\/}}_{2}(r(-1),r(0),r(1))$ $\mskip 4.0mu plus 2.0mu
minus 4.0mu\parallel\mskip 4.0mu plus 2.0mu minus 4.0mu$
${\text{Age\/}}:={\text{Age\/}}+1\bmod U$
} } }

∎

We will also have a field Addr. A colony is a segment of cells with addresses
growing from 0 to $Q-1$ modulo some constant $Q$.

A location is a pair $({\text{F\/}},I)$ where F is a field, and $I$ is an
interval of addresses in the colony. We will denote it as

${\text{F\/}}(I).$

As an element of the language, of course, a location is simply a triple
consisting of the field, and the numbers determining the endpoints of the
interval. A location is meant to specify a sequence of symbols on track F. If
a shorthand name is given a location, this will generally begin with a minus
sign, like

${\text{\\_Info\/}}.$

######  Remark 7.7.

Occasionally, we may treat the union of two or three locations as one. It is
easy to generalize the rules dealing with locations to this case. ∎

Let us be given a string $S$ consisting of a constant number of runs of the
same symbol. For example, $0^{m}1^{n}$ has one run of 0’s and a run of 1’s.
Let us also be given a location loc. Then a rule
${\text{Write\/}}(S,{\text{loc\/}})$, writing the string $S$ to the location
loc, can be written as a conditional rule, as long as there are runs of 0’s
and 1’s:

|  subrule ${\text{Write\/}}(0^{m}1^{n},{\text{F\/}}([a,a+m+n-1]))$ {
---|---
cond {
? $a\leq{\text{Addr\/}}<Q\wedge(a+m)$
! ${\text{F\/}}:=0$
? $a+m\leq{\text{Addr\/}}<Q\wedge(a+m+n)$
! ${\text{F\/}}:=1$
} }

The rule language can contain some definitions of names for constant strings
of symbols, of the form

(7.7)
${\text{Param\/}}_{0}=s_{0},{\text{Param\/}}_{1}=s_{1},\;{\text{Param\/}}_{2}=s_{2},\ldots.$

where $s_{i}$ are some strings. The names ${\text{Param\/}}_{i}$ are allowed
to be used in the rules. Let us even agree that the whole program is nothing
but a sequence of such definitions, where the first string $s_{0}$ is the
sequence of all the rules. In this case, using the name ${\text{Param\/}}_{0}$
in the rules is a kind of self-reference, but its interpretation is clear
since it denotes a definite string.

######  Theorem 7.8 (Rule Language).

There is a string Interpr and an integer $(\text{interpr\\_coe})$ such that
the following holds. If string $P$ is a description of a transition rule Tr
over state set $\SS$ in the above language (along with the necessary
parameters) then the machine Univ defined in (7.6) computes
${\text{Tr\/}}(r_{-1},r_{0},r_{1})$ (possibly padded with $*$’s) from

${\text{Interpr\/}}\sqcup P\sqcup r_{-1}\sqcup r_{0}\sqcup r_{1}$

within computation time $(\text{interpr\\_coe})(|P|+1)^{2}{\|\SS\|}$ and space
$(\text{interpr\\_coe})(|P|+{\|\SS\|}+1)$.

###### Sketch of proof.

A detailed proof would be tedious but routine. Essentially, each line of a
rule program is some comparison involving some fields: substrings of a state
argument $r_{i}$. We have $(|P|+1)$ squared in the time upper bound since we
may have to look up some parameter repeatedly. ∎

From now on, by a rule program Trans_prog of the transition function Tr, we
will understand some string to be interpreted by Interpr.

###  7.4. A basic block simulation

The simulation described here is used just to demonstrate the use of the
notation and to introduce some elements of the later construction in a simple
setting. Let a transition function ${\text{Tr\/}}_{2}$ be given. We want to
define a cellular automaton $M_{1}={\text{CA\/}}({\text{Tr\/}}_{1})$, whose
trajectories simulate the trajectories of
$M_{2}={\text{CA\/}}({\text{Tr\/}}_{2},Q,U)$, with appropriate $Q,U$. Of
course, there is a trivial simulation, when $M_{1}=M_{2}$, but a more general
scheme will be set up here. This simulation is not one of the typical
simulations by a universal medium: the cell-size of $M_{1}$ depends on $M_{2}$
as in Example 3.1. The construction will be summarized in Theorem 7.13 below.

In the construction, we introduce some more notation that can be considered a
shorthand in writing the rules but can also be incorporated into the rule
language (without invalidating Theorem 7.8 (Rule Language)).

####  7.4.1. Overall structure

The transition function ${\text{Tr\/}}_{2}:\SS_{2}^{3}\to\SS_{2}$ to be
simulated is given by a rule program ${\text{Trans\\_prog\/}}_{2}$. To perform
a simulated state transition of $M_{2}$, a colony of $M_{1}$ must do the
following:

Retrieve:

Retrieve the states of the represented neighbor cells from the neighbor
colonies;

Evaluate:

Compute the new state using ${\text{Tr\/}}_{2}$;

Update:

Replace the old represented state with the new one.

The field Addr holds a number between 0 and $Q-1$, as discussed in Subsection
3.1. The default operation is to keep this field unchanged. The time steps
within a work period of a colony are numbered consecutively from 0 to $U-1$.
The field Age holds a number between 0 and $U-1$ intended to be equal to this
number. The default operation is to increase this by 1 modulo $U$. These
default operations will not be overridden in the simple, fault-free
simulations. Using these fields, each cell knows its role at the current stage
of computation.

On the track Info, each colony holds a binary string of length
${\|\SS_{2}\|}$. For a string $S\in\SS_{1}^{Q}$, the decoded value
$\varphi^{*}(S)$ is obtained by taking this binary string. The encoding will
be defined later. The default operation on the information field is to leave
it unchanged. It will be overridden only in the last, updating step. For
simplicity, let us take $|{\text{Info\/}}|=2$, i.e. the Info track contains
only symbols from the standard alphabet. The field Cpt will be used much of
the time like the cells of a standard computing medium, so its size is the
capacity $|{\text{Univ\/}}|={\|\SS_{{\text{Univ\/}}}\|}$ of the fixed
efficiently universal standard computing medium. It has subfields Input,
Output. The field ${\text{Cpt\/}}.{\text{Input\/}}$ is under the control of
the rule Retrieve, while rest of Cpt is under the control of the rule Eval.

The whole program can be summarized as

|  Retrieve;
---|---
Eval;
Update

####  7.4.2. Mail movement

Let $x$ be the base of the current colony under consideration. For $i=-1,0,1$,
we will indicate how to write a subrule

${\text{Copy\/}}(i,{\text{loc\/}}_{1},{\text{loc\/}}_{2})$

that copies, from the colony with base $x-iQ$, the location
${\text{loc\/}}_{1}$ to location ${\text{loc\/}}_{2}$ of the current colony.

######  Remark 7.9.

In the present section, for convenience, we assume that the tracks in
${\text{loc\/}}_{1}$ and ${\text{loc\/}}_{2}$ have the same width. Similarly,
we assume that the mail track is at least as wide than any of the tracks that
it serves during copying. This assumption might not be valid if the transition
function we are designing is separable with some small bandwidth (as in 2.2.1)
since the mail field must be part of Buf.

Copying can be organized also without the assumption. Suppose e.g. that the
mail track and ${\text{loc\/}}_{2}$ is narrow, and the track of
${\text{loc\/}}_{1}$ is wider by a factor $k_{1}$ than these. Then
${\text{loc\/}}_{1}$ can be considered to be the union of $k_{1}$ locations of
smaller width and the copying of ${\text{loc\/}}_{1}$ into
${\text{loc\/}}_{2}$ will need $k_{1}$ separate copying operations. ∎

With the help of this rule, we will have, with appropriate locations
${\text{\\_Retrieved\/}}_{m}$,

|  subrule Retrieve {
---|---
for $m\in\\{-1,0,1\\}$ do {
${\text{Copy\/}}(m,{\text{\\_Info\/}},{\text{\\_Retrieved\/}}_{m})$
} }

here _Info is the location on the Info track containing the represented
string. For the rule Copy we use a framework a little more general than what
would be needed here, with a variable-time version in mind. Let

(7.8) Nb_ind $\displaystyle=\\{-1,0,1\\},$ (7.9) Mail_ind
$\displaystyle=\\{-1.1,-0.1,0.1,1.1\\}.$

In colony with base $x$, track

${\text{Mail\/}}_{k},\ k\in{\text{Mail\\_ind\/}}.$

is for passing information to colony with base $x+\mathop{\rm
sign}\nolimits(k){\lfloor|k|\rfloor}B$, in direction $\mathop{\rm
sign}\nolimits(k)$. Field ${\text{Mail\/}}_{k}$ has subfields

${\text{Fromaddr\/}},{\text{Fromnb\/}},{\text{Info\/}},{\text{Status\/}}.$

For simplicity, let $|{\text{Mail\/}}_{k}.{\text{Info\/}}|=|{\text{Info\/}}|$.
The field Status can have the symbolic values

${\text{Normal\/}},{\text{Undef\/}}.$

The default value of ${\text{Mail\/}}_{k}.{\text{Status\/}}$ is Normal. When
${\text{Mail\/}}_{k}.{\text{Status\/}}={\text{Undef\/}}$ then the other
subfields of ${\text{Mail\/}}_{k}$ will play no role therefore we will,
informally, also write ${\text{Mail\/}}_{k}={\text{Undef\/}}$. For adjacent
cells $x,y$ with $j=y-x$, and their colonies $x^{*}$ and $y^{*}$ (defined from
their Addr field) we define the predicate

${\text{Edge\/}}_{j}(x)=\begin{cases}0&\text{if $x^{*}=y^{*}$,}\\\ 1&\text{if
$x$ and $y$ are endcells of two adjacent colonies,}\\\
\infty&\text{otherwise.}\end{cases}$

The mail track ${\text{Mail\/}}_{k}$ of cell $x$ will cooperate, in direction
$j$, with mail track ${\text{peer\/}}(k,j)$ where

${\text{peer\/}}(k,j)=k-j{\text{Edge\/}}_{j}(x)$

if the latter is in Mail_ind. For $j=-\mathop{\rm sign}\nolimits(k)$, we
define

${\text{Mail\\_to\\_receive\/}}(k)={\text{Mail\/}}_{{\text{peer\/}}(k,j)}^{j}.$

as the mail to be received into ${\text{Mail\/}}_{k}$ provided
${\text{peer\/}}(k,j)\in{\text{Mail\\_ind\/}}$ and Undef otherwise. The one-
step rule Move_mail gets mail from the neighbor cell:

|  subrule Move_mail {
---|---
pfor $k$ in Mail_ind do {
${\text{Mail\/}}_{k}:={\text{Mail\\_to\\_receive\/}}(k)$
} }

Here, pfor is a “parallel for”: the rule is carried out simultaneously for all
$k$ (i.e. for all fields indexed by $k$). A cell will typically copy the
information to be sent into ${\text{Mail\/}}_{k}.{\text{Info\/}}$ and at the
same time, its own address into ${\text{Mail\/}}_{k}.{\text{Fromaddr\/}}$, and
$-\mathop{\rm sign}\nolimits(k){\lfloor|k|\rfloor}$ into
${\text{Mail\/}}_{k}.{\text{Fromnb\/}}$. In the copy rule here,
$i\in\\{-1,0,1\\}$ refers to the direction of the sending colony as seen from
the receiving colony. The next argument is the location of origin in the
sending colony, the one following is the location to receive the information
in the receiving colony.

|  subrule
${\text{Copy\/}}(i,{\text{F\/}}_{1}([a_{1},a_{1}+n-1]),{\text{F\/}}_{2}([a_{2},a_{2}+n-1]))$
{
---|---
let $k=1.1i$ if $i\neq 0$ and $0.1\mathop{\rm sign}\nolimits(a_{2}-a_{1})$
otherwise
let $l=0.1\mathop{\rm sign}\nolimits(k)$
${\text{Mail\/}}_{k}.{\text{Fromaddr\/}}:={\text{Addr\/}}$
$\mskip 4.0mu plus 2.0mu minus 4.0mu\parallel\mskip 4.0mu plus 2.0mu minus
4.0mu$${\text{Mail\/}}_{k}.{\text{Fromnb\/}}:=-i$
$\mskip 4.0mu plus 2.0mu minus 4.0mu\parallel\mskip 4.0mu plus 2.0mu minus
4.0mu$${\text{Mail\/}}_{k}.{\text{Info\/}}:={\text{F\/}}_{1}$;
repeat $2Q$ times {
Move_mail
$\mskip 4.0mu plus 2.0mu minus 4.0mu\parallel\mskip 4.0mu plus 2.0mu minus
4.0mu$cond {
? ${\text{Addr\/}}\in[a_{2},a_{2}+n-1]$ and
${\text{Addr\/}}-a_{2}={\text{Mail\/}}_{l}.{\text{Fromaddr\/}}-a_{1}$ and
$-i={\text{Mail\/}}_{l}.{\text{Fromnb\/}}$
! ${\text{F\/}}_{2}:={\text{Mail\/}}_{l}.{\text{Info\/}}$
} } }

Figure 12. $\text{Copy}(-1,F_{1}([a_{1},a_{1}+n-1]),F_{2}([a_{2},a_{2}+n-1]))$

######  Remark 7.10 (Indirectly given locations).

The description ${\text{F\/}}_{1}([a_{1},a_{2}])$ of a location can fit into a
single field ${\text{F\/}}_{0}$ of some cell. We will allow that some argument
${\text{loc\/}}_{j}$ of the rule
${\text{Copy\/}}(i,{\text{loc\/}}_{1},{\text{loc\/}}_{2})$ is given by a field
${\text{F\/}}_{0}$ this way. This will be done only if $i=0$, i.e. the copying
proceeds within one colony. When executing the copy rule, it will be assumed
that field ${\text{F\/}}_{0}$ of each cell of the colony contains the same
information ${\text{loc\/}}_{j}$. Therefore the rule can be written just as
above, except that some of its parameters are read now from
${\text{F\/}}_{0}$. ∎

####  7.4.3. The evaluation rule

The subrule Eval controls the track ${\text{Cpt\/}}\mathbin{\raise
0.6458pt\hbox{$\smallsetminus$}}{\text{Cpt\/}}.{\text{Input\/}}$. The first
steps of Eval write the interpreter, and the program of the transition
function to be simulated into appropriate locations on the
${\text{Cpt\/}}.{\text{Input\/}}$ track, followed by writing the program
${\text{Trans\\_prog\/}}_{2}$ found as ${\text{Param\/}}_{1}$ after the
present rules (see (7.7)):

|  ${\text{Write\/}}({\text{Interpr\/}},{\text{\\_Interpr\/}})$;
---|---
${\text{Write\/}}({\text{Param\/}}_{1},{\text{\\_Prog\/}})$. (1)

(If ${\text{Tr\/}}_{1}={\text{Tr\/}}_{2}$ (self-simulation) is desired then
write ${\text{Write\/}}({\text{Param\/}}_{0},{\text{\\_Prog\/}})$ in part
(7.4.3) above, and ${\text{Param\/}}_{1}$, after it.) Then
${\text{Param\/}}_{2},\ldots$ will be written after ${\text{Param\/}}_{1}$.
Next, the rule Eval executes

${\text{Copy\/}}(0,{\text{\\_Retrieved\/}}_{m},{\text{\\_Arg\/}}_{m})$

for $m\in{\text{Nb\\_ind\/}}$ where ${\text{\\_Arg\/}}_{m}$ are locations for
the arguments of the transition function on the
${\text{Cpt\/}}.{\text{Input\/}}$ track. For initialization, the rule writes
$*\cdots*$ to the Output track and the rest of the cells (including the
endcells) of the ${\text{Cpt\/}}.{\text{Input\/}}$ track, and 0’s to the track
${\text{Cpt\/}}\mathbin{\raise
0.6458pt\hbox{$\smallsetminus$}}({\text{Cpt\/}}.{\text{Input\/}}\cup{\text{Cpt\/}}.{\text{Output\/}})$.
Then for a sufficient number of steps, the transition function Univ will be
applied to the Cpt track. According to Theorem 7.8 (Rule Language), the
computation finishes in

$(\text{interpr\\_coe})(|{\text{Trans\\_prog\/}}_{2}|+1)^{2}{\|\SS_{2}\|}$

steps, so this number of iterations is sufficient.

######  Remark 7.11.

If the transition function to be simulated is separable as defined in 2.2.1
then what has been computed is not ${\text{Tr\/}}_{2}$ but the auxiliary
function ${\text{Tr\/}}_{2}^{({w})}$. In this, the meaning of field
$[3{w},4{w}-1]$ is an address, of a target field to be changed in the
simulated cell. The evaluation rule will broadcast this number into the field
Target_addr of each cell of the colony (it fits into a single field) to be
used eventually in Update. ∎

The subrule

Update

copies the track ${\text{Cpt\/}}.{\text{Output\/}}$ into track Info.

######  Remark 7.12.

When the transition rule ${\text{Tr\/}}_{2}$ to be simulated is separable (as
in 2.2.1) then the appropriate locations of ${\text{Cpt\/}}.{\text{Output\/}}$
must be copied to the appropriate locations of Info. Some of this copying uses
locations defined in an indirect way as in Remark 7.10, using the field
Target_addr mentioned in Remark 7.11. ∎

####  7.4.4. Summary in a theorem

The encoding $\varphi_{*}$ of a cell state $v$ of $M_{2}$ into a colony of
$M_{1}$ is defined as follows. The string $v$ is written into _Info. The Cpt
track and the mail tracks are set to all 1’s. Each Age field is set to 0. For
all $i$, the Addr field of cell $i$ of the colony is set to $i$.

The theorem below states the existence of the above simulation. As a condition
of this theorem, the parameters

(7.10) ${\text{Trans\\_prog\/}}_{2},{\|\SS_{1}\|},{\|\SS_{2}\|},Q,U$

will be restricted by the following inequalities.

Cell Capacity Lower Bound:

${\|\SS_{1}\|}\geq c_{1}{\lceil\log U\rceil}+|{\text{Univ\/}}|+c_{2}$

where $c_{1},c_{2}$ can be easily computed from the following consideration.
What we really need is
${\|\SS_{1}\|}\geq|{\text{Addr\/}}|+|{\text{Age\/}}|+|{\text{Info\/}}|+|{\text{Mail\/}}|+|{\text{Cpt\/}}|$
where the following choices can be made:

$\displaystyle|{\text{Info\/}}|$ $\displaystyle=2,$
$\displaystyle|{\text{Mail\/}}_{i}|$
$\displaystyle=|{\text{Mail\/}}_{i}.{\text{Fromaddr\/}}|+|{\text{Mail\/}}_{i}.{\text{Fromnb\/}}|+|{\text{Mail\/}}_{i}.{\text{Info\/}}|={\lceil\log
Q\rceil}+2+2,$ $\displaystyle|{\text{Cpt\/}}|$
$\displaystyle=|{\text{Univ\/}}|,$ $\displaystyle|{\text{Addr\/}}|$
$\displaystyle=|{\text{Age\/}}|={\lceil\log U\rceil}.$

Colony Size Lower Bound:

$Q\geq(\text{interpr\\_coe})({\|\SS_{2}\|}+|{\text{Trans\\_prog\/}}_{2}|+\log
U+1).$

With the field sizes as agreed above, this provides sufficient space in the
colony for information storage and computation.

Work Period Lower Bound:

$U\geq
3Q+(\text{interpr\\_coe})(|{\text{Trans\\_prog\/}}_{2}|+1)^{2}{\|\SS_{2}\|}.$

With the field sizes above, this allows sufficient time for the above program
to be carried out.

It is not difficult to find parameters satisfying the above inequalities since
$\log Q\ll Q$.

######  Theorem 7.13 (Basic Block Simulation).

There are strings ${\text{Sim\\_prog\/}}_{0}$, ${\text{Sim\\_prog\/}}_{1}$
such that the following holds. If ${\text{Trans\\_prog\/}}_{2}$,
${\|\SS_{1}\|}$, ${\|\SS_{2}\|}$, $Q$ , $U$ satisfy the above inequalities
then

$\displaystyle{\text{Param\/}}_{0}$
$\displaystyle={\text{Sim\\_prog\/}}_{1},\qquad{\text{Param\/}}_{1}={\text{Trans\\_prog\/}}_{2},$
$\displaystyle{\text{Param\/}}_{2}$
$\displaystyle={\|\SS_{1}\|},\qquad{\text{Param\/}}_{3}={\|\SS_{2}\|},$
$\displaystyle{\text{Param\/}}_{4}$
$\displaystyle=Q,\qquad{\text{Param\/}}_{5}=U$

is a rule program of a transition function ${\text{Tr\/}}_{1}$ such that
${\text{CA\/}}({\text{Tr\/}}_{1})$ has a block simulation of
${\text{CA\/}}({\text{Tr\/}}_{2},Q,U)$. Also, if
${\|\SS_{1}\|},{\|\SS_{2}\|},Q,U$ satisfy the above inequalities with
$\SS_{1}=\SS_{2}$ and ${\text{Trans\\_prog\/}}_{2}={\text{Sim\\_prog\/}}_{0}$
then

$\displaystyle{\text{Param\/}}_{0}$
$\displaystyle={\text{Sim\\_prog\/}}_{0},\qquad{\text{Param\/}}_{1}=\text{empty
string},$ $\displaystyle{\text{Param\/}}_{2}$
$\displaystyle={\|\SS_{1}\|},\qquad{\text{Param\/}}_{3}={\|\SS_{1}\|},$
$\displaystyle{\text{Param\/}}_{4}$
$\displaystyle=Q,\qquad{\text{Param\/}}_{5}=U$

is a rule program of a transition function ${\text{Tr\/}}_{1}$ such that
${\text{CA\/}}({\text{Tr\/}}_{1})$ has a block simulation of
${\text{CA\/}}({\text{Tr\/}}_{1},Q,U)$.

The given construction is essentially the proof. Its complete formalization
would yield ${\text{Sim\\_prog\/}}_{0}$ and ${\text{Sim\\_prog\/}}_{1}$
explicitly.

##  8\. Robust media

This section defines a special type of one-dimensional medium called robust.
From now on, when we talk about a medium with no qualification we will always
mean a robust medium. For help in understanding the definition can be compared
to the primitive variable-period media in Subsection 6.3. The media defined in
the present section have some features distinguishing them from cellular
automata: non-lattice cells, damage, communication among non-nearest
neighbors. The need for non-lattice cells was explained in Subsection 4.3.

###  8.1. Damage

Robust media have a special set of states ${\text{Bad\/}}\subset\SS$. For a
space-time configuration $\eta$ we define the damage set

${\text{Damage\/}}(\eta)=\mathopen{\\{}\,(x,t):\eta(x,t)\in{\text{Bad\/}}\,\mathclose{\\}}.$

For a space configuration, the damage is defined similarly. The interpretation
of the set ${\text{Damage\/}}(\eta)$ is that when
$(x,t)\in{\text{Damage\/}}(\eta)$ then in the neighborhood of $(x,t)$, we will
not be able to make any predictions of $\eta$, i.e. in some sense, $\eta$
behaves completely “lawlessly” there. When $\eta(x,t)\in{\text{Bad\/}}$ then
it is irrelevant whether we regard site $x$ occupied by a cell or not. For a
cell $x$ a time interval $I$ is damage-free if $\eta(x,\cdot)$ is not in Bad
during $I$.

######  Remark 8.1.

In all cellular media concerned with our _results_ we could require
${\text{Damage\/}}(\eta)=\emptyset$. The damage concept is necessary only in a
trajectory $\eta_{2}$ of a medium $M_{2}$ obtained by simulation from a
trajectory $\eta_{1}$ of some medium $M_{1}$. Such a simulation typically
requires some structure in $\eta_{1}$. When noise breaks down this structure
the predictability of $\eta_{2}$ suffers and this will be signalled by the
occurrence of damage in $\eta_{2}$.

However, for convenience, we will define damage even in the media used on the
lowest level, as a violation of a certain transition rule. ∎

According to the general definition of a medium, the set of trajectories will
be defined by a pair ${b}(\cdot),{g}(\cdot,\cdot,\cdot)$ where ${b}(\alpha)$
give the probability bound belonging to type $\alpha$ and $g(\alpha,W,\eta)$
is the event whose probability is bounded. We formulate these in terms of
“properties”. For a medium with cellsize $B$, let

(8.1) $V=[-B/4,B/4-]\times[-{T_{\bullet}}/4+,0].$

The Computation Property constrains the kinds of events that can occur under
the condition that the damage does not intersect certain larger rectangles.
One condition type $\alpha({\text{restor\/}})$ will be called the Restoration
Property: it bounds the probability of occurrence of damage in the middle of
some window $(x,t)+2V$. The Restoration Property, which depends on a new
parameter $\varepsilon$, says that the probability of the damage is small:
even if other damage occurs at the beginning of a window it will be eliminated
with high probability.

Figure 13. The Restoration Property

######  Condition 8.2 (Restoration Property).

Let ${b}(\alpha({\text{restor\/}}))=\varepsilon$. Further, for any rational
pair $(x,t)$ let

${g}{\bigl{(}\,\alpha({\text{restor\/}}),(x,t)+2V,\eta\,\bigr{)}}$

be the event function for the event that there is damage in $\eta((x,t)+V)$. ∎

The Restoration axiom says that damage, i.e. the occasional obstacle to
applying the Computation Property, disappears soon after its occurrence:
namely, it has very small conditional probability of occurrence in the inner
half of any rectangle $(x,t)+2V$.

The axiom will be automatically satisfied on the lowest level by the property
of the medium that the transition rule is only violated with small
probability.

######  Remark 8.3.

In the model of [11], the restoration axiom is weaker. There, damage does not
necessarily disappear in a short time but if it is contained in a certain kind
of triangle at the beginning of the window then, with high probability, it is
contained in a smaller triangle of the same kind later in the window. ∎

Damage helps us present a hierarchical construction as a sequence of
simulations. When a large burst of faults destroys the fabric of these nested
simulations, then $\eta^{k+1}$ cannot be explained just in terms of the
$\eta^{k}$ from which it is decoded. The damage set will cover those lower-
level details of the mess that we are not supposed to see as well as the
mechanism of its removal. Damage points can be viewed as holes in the fabric
of the lawful parts of a trajectory

Figure 14. Cause for damage in point $(x,t)$ of the simulated trajectory

Consider a simulation $\eta^{*}=\Phi^{*}(\eta)$ between two robust media. Let
us define the damage set of $\eta^{*}$ to be used in almost all such
simulations. As usual, let us mark by ∗ the corresponding quantities in the
simulated medium when some simulation is fixed. We will define
$\eta^{*}(x,t)\in{\text{Bad\/}}$ iff ${\text{Damage\/}}(\eta)$ contains at
least two points $u,v$ such that $u+2V$, $v+2V$ are disjoint and even
$u+3V,v+3V$ are contained in $(x,t)+4V^{*}+(B^{*}/2,0)$.

The value of $s$, provided it is not in Bad, will be essentially defined by a
block code $\varphi$ as

$\varphi^{*}(\eta(x+[0,QB-1],t)).$

However, there will be some look-back in time for stabilization, i.e. the
simulation will not be memoryless. The goal of the damage definition is to
relieve us of the need of simulating a transition function if there is too
much damage in the big rectangle $(x,t)+4V^{*}+(B^{*}/2,0)$.

######  Lemma 8.4 (Simulation Damage Probability Bound).

Let $M$, $M^{*}$ be media with parameters $\varepsilon$, $\varepsilon^{*}$
whose local condition system is defined by the Restoration Property. Let a
simulation $\Phi^{*}$ be defined between them which assigns damage in $M^{*}$
according to the above damage map. If

$\varepsilon^{*}\geq
25((B^{*}/B)({T_{\bullet}}^{*}/{T_{\bullet}})\varepsilon)^{2}$

then, $\Phi^{*}$ is a deterministic canonical simulation map as defined in
6.2.1.

This lemma says that small bursts of damage that are not too close to each
other behave in the medium $M$ as if they were independent, therefore the
probability of the occurrence of two such bursts can be estimated by
$\varepsilon^{2}$ times the number of such pairs in a rectangle $V^{*}$.

###### Proof.

It is enough to show an expression of the form (6.12) for local conditions of
type restor in $M^{*}$. Let $x_{1},t_{1}$ be the sizes of the space and time
projections of $V$. We define the following lattice of points:

$\mathcal{V}=\mathopen{\\{}\,(ix_{1},jt_{1}):i,j\in\mathbb{Z}\,\mathclose{\\}}.$

Then the rectangles $v+V$ for $v\in\mathcal{V}$ form a partition of the space-
time. For each $u$ in space-time, let $v(u)$ be the $v\in\mathcal{V}$ with
$u\in v+V$. Let $\eta$ be a trajectory of $M$. It is enough to consider the
rectangle $2V^{*}$. If ${\text{Damage\/}}(\eta^{*})$ intersects $V^{*}$ then
there are some points $u_{1},u_{2}$ in ${\text{Damage\/}}(\eta)$ such that
$u_{i}+2V$ are disjoint and even $u_{i}+3V$ are in $5V^{*}+(B^{*}/2,0)$. Then
it is easy to see that even $v(u_{i})+2V$ are disjoint from each other and are
contained in $5V^{*}+(B^{*}/2,0)$. Let $n$ be the number of pairs
$v_{1},v_{2}$ in $\mathcal{V}$ with this property. We found $n$ pairs of
rectangles $u_{i,j}+2V$ ($i=1,\ldots,n$, $j=1,2$) such that $u_{i,1}+2V\cap
u_{i,2}+2V=\emptyset$, and that if ${\text{Damage\/}}(\eta^{*})$ intersects
$V^{*}$ then there is an $i$ such that ${\text{Damage\/}}(\eta)$ intersects
$u_{i,j}+V$ for $j=1,2$. We found

${g}^{*}({\text{restor\/}},2V^{*},\eta^{*})\leq\sum_{i}\prod_{j}{g}{\bigl{(}\,{\text{restor\/}},u_{i,j}+2V,\eta\,\bigr{)}}.$

To complete the proof, observe that

$\sum_{i}\prod_{j}{b}({\text{restor\/}})\leq n\varepsilon^{2}$

Since counting shows $n<25((B^{*}/B)({T_{\bullet}}^{*}/{T_{\bullet}}))^{2}$
and the assumption of the lemma says
$25((B^{*}/B)({T_{\bullet}}^{*}/{T_{\bullet}}))^{2}\varepsilon^{2}<\varepsilon^{*}$
both conditions of a deterministic canonical simulation are satisfied. ∎

###  8.2. Computation

####  8.2.1. Neighborhood structure

Before giving the Computation Property, let us introduce some details of the
structure of a robust medium. Cells sometimes have to be erased (killed) in a
trajectory since cells created by the damage may not be aligned with the
original ones. At other times, the creation of a live cell at a vacant site
will be required. Most of the trajectory requirements of a robust medium will
be expressed by a transition function Tr, desribed later. Killing and creation
may be indicated by some special values of this function.

Although we permit non-lattice configurations we could still use a transition
function that restricts the new state of a cell only as a function of adjacent
cells. It is, however, convenient to allow nearby cells to see each other
regardless of whether they are on the same lattice or not. We extend the
notation $\vartheta_{j}(x)$ introduced in Subsection 7.3. Let us fix $\eta$.
For a vacant site $x$ at time $t$ there is at most one cell at distance
greater than 0 but less than $B$ to the right of $x$: if it exists and there
is no damage between it and $x$ then we denote it by
$\vartheta_{0.5}(x,t,\eta)$. Otherwise, $\vartheta_{0.5}(x,t,\eta)$ is
undefined. The notation $\vartheta_{-0.5}$ is defined analogously. We will
omit $\eta$, and sometimes even $t$, from the arguments when it is obvious
from the context. By convention, whenever $\vartheta_{j}(x,t,\eta)$ is
undefined then let

$\eta(\vartheta_{j}(x,t,\eta),t)={\text{Vac\/}}.$

For a (nonvacant) cell $x$ there is at most one cell at distance greater than
$B$ but smaller than $2B$ to the right of $x$: if it exists and there is no
damage between it and $x$ then we denote it by

$\vartheta_{1.5}(x).$

Otherwise, this value is undefined. The corresponding cell to the left is
denoted by $\vartheta_{-1.5}(x)$. The medium depends on a parameter $r$ called
the reach, determining the maxiumum distance of the neighbors that a cell is
allowed to depend on directly. (We will only use two possible reaches: $r=1$
and $r=3$.) Let

(8.2) ${\text{Nb\\_ind\/}}_{r}=\\{-1.5,1.5\\}\cup\\{-r,-r+1,\ldots,r-1,r\\}.$

A function ${\mathbf{u}}\colon{\text{Nb\\_ind\/}}_{r}\to\SS$ will be called an
assignment. For an assignment ${\mathbf{u}}$, we will write $u_{j}$ for the
value of ${\mathbf{u}}$ on $j$. The transition function in a robust medium has
the form ${\text{Tr\/}}({\mathbf{u}})$ where ${\mathbf{u}}$ runs over
assignments. In analogy with (2.3), let

$\overline{{\text{Tr\/}}}(\eta,x,t)={\text{Tr\/}}({\mathbf{u}})$

where ${\mathbf{u}}$ is the assignment defined by
$u_{j}=\eta(\vartheta_{j},t)$ with $\vartheta_{j}=\vartheta_{j}(x,t,\eta)$
except that if $\vartheta_{j}$ is defined for some noninteger $j$, then then
$u_{\lambda j}={\text{Vac\/}}$ for all $\lambda>1$. Thus, when a closest
neighbor $\vartheta_{j}$ is not adjacent then the transition function does not
depend on any farther neighbors in that direction. $\eta$ will be omitted from
${\text{Tr\/}}(\eta,x,t)$ when it is obvious from the context.

####  8.2.2. Properties of the transition function

A robust medium will be denoted by

${\text{Rob\/}}({\text{Tr\/}}^{({w})},B,{T_{\bullet}},{T^{\bullet}},\varepsilon,\varepsilon^{\prime},r).$

The set $\SS$ of states is implicit in the transition function. Similarly, the
subset Bad of states will be defined implicity by the transition function:
this will be the states such that if any argument of the transition function
is in this set, the function value is not defined. The first bit of the state
of a cell will be called Rand and we write
${\text{Det\/}}={\text{All\/}}\mathbin{\raise
0.6458pt\hbox{$\smallsetminus$}}{\text{Rand\/}}$. There is also a subfield
${\text{Color\/}}\subset{\text{Det\/}}$ defined implicitly by the transition
function: this is, say, the set of those first bits of Det that turn to 0 when
Tr is applied to the vector with all Vac values. (Color plays role in self-
organization.)

The transition function, a mapping from assignments to $\SS$, describes the
goal for the deterministic part $s.{\text{Det\/}}$ of the value $s$ of the
state after transition. We will see that the field Color will not necessarily
obey the transition function. We will assume that Tr is separable in the sense
of 2.2.1 with some bandwidth ${w}$. Let the fields Rand and Color be part of
Inbuf: thus, they can be seen by a neighbor cell in a single step. The
separability requirement also defines a predicate
${\text{legal\/}}^{{\text{Tr\/}}}(u,v)$.

Our transition functions in robust media will also have the following
properties:

######  Condition 8.5 (Time Marking).

If $s\neq{\text{Vac\/}}$ then ${\text{legal\/}}(s,s)=0$. ∎

This condition is similar to (6.17) and says that a nonvacant cell always
tries to change its state. It is necessary for nontrivial media with a strict
dwell period upper bound.

Let us call a pair $(j,v)\in\\{-1,1\\}\times\SS$, a potential creator of state
$s\neq{\text{Vac\/}}$ if $s={\text{Tr\/}}({\mathbf{u}})$ provided $u_{i}=v$
for $i=j$ and Vac otherwise. In a space-time configuration $\eta$, at a
switching time $\sigma$ of cell $x$ when $\eta(x,t)$ turns from vacant to non-
vacant, we call $y=\vartheta_{j}(x,\sigma-)$ a creator of $x$ for time
$\sigma$ if $(j,\eta(\vartheta_{j}(x,\sigma-)))$ is a potential creator of
$\eta(x,\sigma)$ and further $\eta(x,t)={\text{Vac\/}}$,
$\eta(y,t)=\eta(y,\sigma-)$ for $t\in[\sigma-{T_{\bullet}}/2+,\sigma-]$.

######  Condition 8.6 (Creation).

Let ${\mathbf{u}}$ be an assignment such that $u_{0}={\text{Vac\/}}$,
${\text{Tr\/}}({\mathbf{u}}).{\text{Det\/}}\neq{\text{Vac\/}}.{\text{Det\/}}$
and in which there is a $j$ in $\\{-1,1\\}$ with $u_{j}\neq{\text{Vac\/}}$.
Then there is a $j\in\\{-1,1\\}$ such $(j,u_{j})$ is a potential creator of
${\text{Tr\/}}({\mathbf{u}})$. ∎

This condition says that if, for some $t_{1}<t_{2}$, a vacant cell $x$ comes
to life at time $t_{2}$ due to “observation” at some time $t_{1}$ when there
is a neighbor $\vartheta_{j}(x,t_{1})$ nearby then an adjacent neighbor at
time $t_{1}$ can be made completely responsible for the state of the new cell
at time $t_{2}$: the state would be the same even if all other sites in the
neighborhood were vacant.

If ${\mathbf{u}}$ is the neighborhood state assignment vector consisting of
all vacant states then let ${\text{Newborn\/}}={\text{Tr\/}}({\mathbf{u}})$ be
the canonical newborn state. A state $s$ is a newborn state if

$s.({\text{Det\/}}\mathbin{\raise
0.6458pt\hbox{$\smallsetminus$}}{\text{Color\/}})={\text{Newborn\/}}.({\text{Det\/}}\mathbin{\raise
0.6458pt\hbox{$\smallsetminus$}}{\text{Color\/}}).$

Note that a newborn state is allowed to be somewhat less determined than
others: this property will be used in self-organization.

######  Condition 8.7 (Cling to Life).

If ${\text{Tr\/}}(\eta,x,t)={\text{Vac\/}}$ then
$\eta(\vartheta_{j}(x,t),t)\neq{\text{Vac\/}}$ for some $j\in\\{-1.5,1.5\\}$.
∎

Thus a cell will only be erased if it may disturb a close non-aligned
neighbor.

####  8.2.3. The computation axiom

The condition called the Computation Property has a form similar to the
definition of primitive variable-period media in Subsection 6.3. For a space-
time configuration $\eta$, cell $x$ and rational number $a>0$ let

$\sigma_{1},\sigma_{2},\sigma_{0}$

be defined as follows. $\sigma_{1},\sigma_{2}$ are the first two switching
times of $x$ after $a$ but defined only if
$\eta(x,\sigma_{1})\neq{\text{Vac\/}}$. On the other hand, $\sigma_{0}$ is the
first switching time of $x$ after $a+{T^{\bullet}}$ but defined only if
$\eta(x,a+{T^{\bullet}})={\text{Vac\/}}$. Whenever we have an event function
${g}(\alpha,W,\eta)$ in whose definition $\sigma_{2}$ occurs, this function is
always understood to have value 0 if $\sigma_{2}$ is not defined (similarly
with $\sigma_{0}$).

Figure 15. To the computation axiom. The large rectangle is $W_{1}(x,a)$. The
rectangle of the same height but width 0 at point $x$ is $W_{0}(x,a)$. The
small rectangle between times $\sigma_{1}$ and $\sigma_{2}$ is the cell work
period under consideration. Its lower part is the observation period.

Let

$\displaystyle W_{0}(x,a)$
$\displaystyle=\\{x\\}\times[a-{T_{\bullet}}/2+,a+2{T^{\bullet}}],$
$\displaystyle W_{1}(x,a)$
$\displaystyle=[x-(r+1)B,x+(r+2)B-]\times[a-{T_{\bullet}}/2+,a+2{T^{\bullet}}],$
$\displaystyle{f}_{j}(x,a,\eta)$ $\displaystyle=\text{the event function for
}\mathopen{\\{}\,{\text{Damage\/}}(\eta)\cap
W_{j}(x,a)=\emptyset\,\mathclose{\\}}\qquad(j=0,1).$

######  Condition 8.8 (Computation Property).

This axiom consists of several condition types. For each type $\alpha$ used in
this axiom except $\alpha({\text{rand\/}},j)$, we have ${b}(\alpha)=0$, i.e.
the corresponding events ${g}(\alpha(),W,\eta)$ are simply prohibited in the
trajectory. On the other hand,

${b}(\alpha({\text{rand\/}},j))=0.5+\varepsilon^{\prime}\quad(j=0,1).$

  1. (a)

This condition requires coin-tossing, for $j=0,1$:

${g}{\bigl{(}\,\alpha({\text{rand\/}},j),\;W_{0}(x,a),\;\eta\,\bigr{)}}={f}_{0}(x,a,\eta)\\{\eta(x,\sigma_{2}).{\text{Rand\/}}=j\\}.$

  2. (b)

This prohibits dwell periods shorter than ${T_{\bullet}}$ or longer than
${T^{\bullet}}$. Let

${g}{\bigl{(}\,{\text{dw\\_p\\_bd\/}},\;W_{0}(x,a),\;\eta\,\bigr{)}}={f}_{0}(x,a,\eta){h}({\text{dw\\_p\\_bd\/}},x,a,\eta)$

where ${h}({\text{dw\\_p\\_bd\/}},x,a)=1$ if $\eta$ has a dwell period shorter
than ${T_{\bullet}}$ in $W_{0}(x,a)$ or has a dwell period longer than
${T^{\bullet}}$ there (and, as always, 0 otherwise).

  3. (c)

This says that whenever $W_{0}(x,a)$ is damage-free the transition at
$\sigma_{2}$ is a legal one. Let

${g}{\bigl{(}\,{\text{legal\\_comp\/}},\;W_{0}(x,a),\;\eta\,\bigr{)}}={f}_{0}(x,a,\eta)(1-{\text{legal\/}}(\eta(x,\sigma_{2}-),\eta(x,\sigma_{2}))).$

  4. (d)

This says that whenever $W_{0}(x,a)$ is damage-free the transition in
$\sigma_{0}$ is a legal one. Let

${g}{\bigl{(}\,{\text{legal\\_birth\/}},\;W_{0}(x,a),\;\eta\,\bigr{)}}={f}_{0}(x,a,\eta)(1-{\text{legal\/}}(\eta(x,\sigma_{0}-),\eta(x,\sigma_{0}))).$

  5. (e)

This says that whenever $W_{1}(x,a)$ is damage-free the transition function
applies, at least as much as it can, based on observation at a certain time
during the observation period (“atomicity”). Let

${g}{\bigl{(}\,{\text{trans\/}},\;W_{1}(x,a),\;\eta\,\bigr{)}}={f}_{1}(x,a,\eta){h}({\text{trans\/}},x,a,\eta)$

where ${h}({\text{trans\/}},x,a,\eta)=1$ unless there is a
$t^{\prime}\in[\sigma_{1}+,\sigma_{2}-{T_{\bullet}}/2]$ with

$\eta(x,\sigma_{2}).{\text{Det\/}}={\text{Tr\/}}(\eta,x,t^{\prime}).{\text{Det\/}}.$

  6. (f)

This says that if $x$ always has a neighbor during the whole interval of
interest before its birth then it has a creator. Let

${g}{\bigl{(}\,{\text{creator\/}},\;W_{1}(x,a),\;\eta\,\bigr{)}}={f}_{1}(x,a,\eta){h}({\text{creator\/}},x,a,\eta)$

where ${h}({\text{creator\/}},x,a,\eta)=1$ unless either $x$ has a creator for
time $\sigma_{0}$ or there is a $t^{\prime}\in[a+,\sigma_{0}]$ such that
$\eta(\vartheta_{j}(x,t^{\prime}),t^{\prime})={\text{Vac\/}}$ for all
$j\in\\{-1,1\\}$.

  7. (g)

This says that if $x$ does not have a creator accounting for its birth then it
is a newborn with vacant neighbors at some time shortly before birth. Let

${g}{\bigl{(}\,{\text{newborn\/}},\;W_{1}(x,a),\;\eta\,\bigr{)}}={f}_{1}(x,a,\eta){h}({\text{newborn\/}},x,a,\eta)$

where ${h}({\text{newborn\/}},x,a,\eta)=1$ if $x$ has no creator for time
$\sigma_{0}$, and either $\eta(x,\sigma_{0})$ is not newborn state or there is
no $t$ in $[\sigma_{0}-{T_{\bullet}}/2,\sigma_{0}-]$ with
$\eta(\vartheta_{j}(x,t),t)={\text{Vac\/}}$ for all $j\in{\text{Nb\\_ind\/}}$.

  8. (h)

This says that $x$ cannot stay vacant if it has would-be creators for a long
time and has no neighbor blocking creation. Let

${g}{\bigl{(}\,{\text{no\\_birth\/}},\;W_{1}(x,a),\;\eta\,\bigr{)}}={f}_{1}(x,a,\eta){h}({\text{no\\_birth\/}},x,a,\eta)$

where ${h}({\text{no\\_birth\/}},x,a,\eta)=1$ if

    1. (a)

$\eta(x,t)={\text{Vac\/}}$ for all $t\in[a+,a+2{T^{\bullet}}]$;

    2. (b)

for each $t\in[a+,a+2{T^{\bullet}}]$ there is a $j\in\\{-1,1\\}$ such that
$(j,\vartheta_{j}(x,t))$ is a potential creator of some (non-vacant) state;

    3. (c)

there is no $(y,t)$ with $0<|y-x|<B$, $t\in[a+,a+2{T^{\bullet}}]$,
$\eta(y,t)\neq{\text{Vac\/}}$;

∎

######  Example 8.9 (Special cases).

To obtain a constant-period medium as a special case of robust media set
${T_{\bullet}}={T^{\bullet}}$, $r=1$. To obtain a deterministic cellular
automaton, set also $\varepsilon=0$, require that the space-time
configurations have empty damage and that the transition function does not
give a vacant value.

The connection between primitive variable-period media and robust media will
be set up using a trivial simulation. Let
$M_{1}={\text{Prim\\_var\/}}({\text{Tr\/}},B,{T_{\bullet}},{T^{\bullet}},\varepsilon)$.
We define a simple simulation $\Phi^{*}$ by this medium of the robust medium

$M_{2}={\text{Rob\/}}({\text{Tr\/}},B,{T_{\bullet}},{T^{\bullet}},\varepsilon,\varepsilon,1).$

$M_{2}$ has almost the same state set as $M_{1}$ except that it also has at
least one extra state, making the set Bad nonempty. We give the definition of
$s=\eta^{*}(x,t)=\Phi^{*}(\eta)(x,t)$ for each $\eta$. If $x$ is not an
integer multiple of $B$ then $s={\text{Vac\/}}$. Else $s=\eta(x,t)$ unless
$\eta$ violates the Computation Property of $M_{2}$ at $x$ with
$\sigma_{2}=t$: in that case, it is in Bad. It can be verified that this is
indeed a simulation. ∎

####  8.2.4. Error-correction

The error-correction property can be defined here just as in 3.6.2, replacing
$T_{i}$ with ${T_{\bullet}}_{i}$. Then a lemma analogous to Lemma 3.7 can be
formulated, and a proof for Theorem 6.13 can be provided that is analogous to
the proof of Theorem 2.5.

###  8.3. Simulating a medium with a larger reach

######  Theorem 8.10 (Reach Extension).

For all $r$ and all ${\text{Tr\/}}_{2}$ with reach $r$, for all
${T_{\bullet}}\leq{T^{\bullet}}$ let
$\lambda={\lceil{T^{\bullet}}/{T_{\bullet}}\rceil}$,

$U=64\lambda((\lambda+1)r+1)(r+2).$

There is a set $\SS_{1}$, a one-to-one mapping $s\mapsto s_{*}$ from $\SS_{2}$
to $\SS_{1}$ giving rise to the code $\varphi_{*}(\xi)(x)=(\xi(x))_{*}$,
functions ${\text{Tr\/}}_{1}()$ of reach 1, and for all
$B,\varepsilon,\varepsilon^{\prime}$, a decoding $\Phi^{*}$ such that
$(\Phi^{*},\varphi_{*})$ is a simulation of

$M_{2}={\text{Rob\/}}({\text{Tr\/}}_{2},B,U{T_{\bullet}},U{T^{\bullet}},U\varepsilon,UR\varepsilon^{\prime},r)$

by

$M_{1}={\text{Rob\/}}({\text{Tr\/}}_{1},B,{T_{\bullet}},{T^{\bullet}},\varepsilon,\varepsilon^{\prime},1).$

The basic idea is of the proof is to replicate the state of a whole reach-$r$
neighborhood of a cell of $M_{2}$ in a single cell of $M_{1}$. It will take
then a work period size $U$ that is at least proportional to $r$ for a cell of
$M_{1}$ to simulate a step of a cell of $M_{2}$ since the cell must learn
about neighbors $r$ steps away. In fact, due to asynchrony, the work period
will be significantly larger. Some complication is due to the need to achieve
the “atomicity” property, namely that a single observation time can be
assigned to a transition of $M_{1}$ even though the observation occurs over an
extended period of time. The solution for this is to make sure that the
observed values coming from the neighbor cells do not come from near the end
of the work period of those cells.

##  9\. Amplifiers

In the present section, when we talk about media without qualification we
understand robust media.

###  9.1. Amplifier frames

The eventual goal is to find an amplifier $(M_{k},\Phi_{k})$ with a fast
decreasing sequence $\varepsilon_{k}$ and we also want $M_{k}$ to simulate a
computation with transition function Univ and damage probability bound
$\varepsilon_{k}$. In this subsection, we impose some conditions on the
parameters of a sequence $(M_{k})$ of media that are sufficient for the
existence of an amplifier. These conditions are similar to the inequalities in
the conditions of Theorem 7.13.

####  9.1.1. The rider fields

All robust media $M_{k}$ have, by definition, the fields Det and Rand whose
behavior is governed by the computation and restoration properties. Only Det
will be subdivided into subfields: therefore subfields
$\eta.{\text{Det\/}}.{\text{F\/}}$ will be denoted simply as
$\eta.{\text{F\/}}$, without danger of confusion.

In the media $M^{k}$ we discuss further, there will be a shared field called
${\text{Rider\/}}^{k}$ with guard field ${\text{Guard\/}}^{k}$ (see Subsection
4.2). The useful computation of $M_{k}$ will be carried out on the “active
level” $k$, on the track ${\text{Rider\/}}^{k}$. The simulations will have
sufficient freedom in the rule governing ${\text{Rider\/}}^{k}$ on the active
level to regain the universality lost by having no “program” for the whole
simulation (as discussed in Subsection 4.3). We will say that in a robust
medium $M$, the transition function Tr, with state set $\SS$, is combined from
the rider transition function Rd_trans and simulation transition function
Sim_trans with fields Rider and Guard, if the value
$s={\text{Tr\/}}({\mathbf{r}})$ is defined in the following way. If
${\text{Sim\\_trans\/}}({\mathbf{r}})={\text{Vac\/}}$ then $s={\text{Vac\/}}$.
Otherwise, all fields of $s$ disjoint from
$s.({\text{Rider\/}}\cup{\text{Guard\/}})$ are defined by
${\text{Sim\\_trans\/}}({\mathbf{r}})$. Further

(9.1) $\displaystyle s.{\text{Rider\/}}$
$\displaystyle=\begin{cases}{\text{Rd\\_trans\/}}({{\mathbf{r}}}).{\text{Rider\/}}&\text{if
$r_{0}.{\text{Guard\/}}=0$,}\\\
{\text{Sim\\_trans\/}}({{\mathbf{r}}}).{\text{Rider\/}}&\text{otherwise,}\end{cases}$
$\displaystyle s.{\text{Guard\/}}$
$\displaystyle=\begin{cases}{\text{Rd\\_trans\/}}({{\mathbf{r}}}).{\text{Guard\/}}&\text{if
$r_{0}.{\text{Guard\/}}\geq 0$,}\\\
{\text{Sim\\_trans\/}}({{\mathbf{r}}}).{\text{Guard\/}}&\text{otherwise.}\end{cases}$

Thus, the rider field is controlled by its own transition function only when
the simulation does not command to eliminate the cell, and when we are on the
active level according to the guard field. The guard field will be controlled
by its own transition function in case we are not below the active level
(where the simulation transition function will enforce the broadcast property
for it).

####  9.1.2. Broadcast amplifier frames

The string prog will be called a uniform program (with complexity coefficient
$c$) for the functions $f_{k}$ if there is some constant $c$ such that it
computes on the universal computing medium Univ the value
$f_{k}({{\mathbf{r}}})$ from $k,{{\mathbf{r}}}$ with space- and time-
complexities bounded by $c(\log k+|{\mathbf{r}}|)$ where $|{\mathbf{r}}|$ is
the total number of bits in the arguments ${\mathbf{r}}$. If a sequence
$(f_{k})$ of functions has a uniform program it is called uniform. As a
special case, a sequence of constants $c_{k}$ is uniform if it is computable
with space- and time complexities $c\log k$ from the index $k$.

Here, and always from hence, when we refer to a natural number $k$ as a binary
string we always mean its standard binary representation. We will distinguish
the simpler notion of a “broadcast amplifier frame” from the full-featured
“amplifier frame”. The simpler notion is sufficient for the basic non-
ergodicity result. A broadcast amplifier frame Frame is given by sequences

${\text{Cap\/}}_{k},Q_{k},U_{k},$

and the constant $R_{0}$ satisfying certain conditions. Here, $Q_{k}$ is the
number of cells in a colony. For an appropriate sequence $\nu_{k}\geq 1$, the
number of dwell periods in a work period will be allowed to vary between
$U_{k}/\nu_{k}$ and $U_{k}\nu_{k}$. Given a frame Frame, let us define some
additional parameters as follows, with some arbitrary positive initial
constants ${T^{\bullet}}_{1}\geq{T_{\bullet}}_{1}$ and
$\varepsilon=\varepsilon_{1},\varepsilon^{\prime}_{1}<1/R_{0}^{2}$.

(9.2) $\displaystyle\SS_{k}$ $\displaystyle=\\{0,1\\}^{{\text{Cap\/}}_{k}},$
$\displaystyle B_{k}$ $\displaystyle=\prod_{i<k}Q_{i},$ $\displaystyle\nu_{k}$
$\displaystyle=1+R_{0}Q_{k}/U_{k}\text{ if
}{T_{\bullet}}_{1}\neq{T^{\bullet}}_{1},\text{ and 1 otherwise}.$
$\displaystyle{T_{\bullet}}_{k}$
$\displaystyle={T_{\bullet}}_{1}\prod_{i=1}^{k-1}U_{i}/\nu_{i},$
$\displaystyle{T^{\bullet}}_{k}$
$\displaystyle={T^{\bullet}}_{1}\prod_{i=1}^{k-1}U_{i}\nu_{i},$
$\displaystyle\varepsilon_{k+1}$
$\displaystyle=25(Q_{k}U_{k}\nu_{k}\varepsilon_{k})^{2},$
$\displaystyle\varepsilon^{\prime\prime}_{k}$
$\displaystyle=4Q_{k}U_{k}\nu_{k}\varepsilon_{k},$
$\displaystyle\varepsilon^{\prime}_{k}$
$\displaystyle=\varepsilon^{\prime}_{1}+\sum_{i=1}^{k-1}\varepsilon^{\prime\prime}_{i}.$

The formula for $\varepsilon_{k+1}$ is natural in view of Lemma 8.4. The
definition of $\varepsilon^{\prime}_{k+1}$ takes into account the limited
ability to simulate a coin-toss with the help of other coin-tosses.
$\varepsilon^{\prime\prime}_{k}$ is used for the error-correction property: it
is essentially the probability that there is any $k$-level damage at all
during the work period of a colony of $k$-cells. The requirements below
defining an amplifier frame can be compared to the corresponding conditions
for Theorem 7.13.

An object Frame given by the above ingredients is a broadcast amplifier frame
if the conditions listed below hold.

Complexity Upper Bounds:

All parameters in Frame are uniform sequences with complexity coefficient
$R_{0}$;

Bandwidth Lower Bound:

We should be able to deal with numbers comparable to the size of the colony
and the work period within a cell:

(9.3) ${\text{Cap\/}}_{k}\geq R_{0}\log U_{k};$

Capacity Lower Bound:

The colony must represent the state of the big cell with redundancy:

(9.4) $R_{0}{\text{Cap\/}}_{k+1}\leq Q_{k}{\text{Cap\/}}_{k}.$

Work Period Lower Bound:

There must be enough dwell periods in a work period to perform the necessary
computations of a simulation, with some repetitions:

(9.5) $U_{k}\geq R_{0}(\log Q_{k}+\log k)Q_{k}.$

The factor $\log Q_{k}+\log k$ is needed only for technical reasons, in the
proof of self-organization.

Error Upper Bound:

The following upper bound on $Q_{k}U_{k}$ implies, in view of the definition
of the error probabilities, that these decrease exponentially:

(9.6) $\varepsilon_{k}^{0.2}\leq R_{0}/Q_{k}U_{k}.$

Time Stability:

(9.7) $\frac{{T^{\bullet}}_{k}}{{T_{\bullet}}_{k}}\leq 3.$

This inequality (which is made this strong for simplicity) can be achieved
e.g. with $U_{k}\geq ck^{2}Q_{k}$ for some sufficiently large $c$.

The definition of $\varepsilon_{k+1}$ and (9.7), implies

$\varepsilon_{k+1}=25(Q_{k}{T^{\bullet}}_{k+1}/{T^{\bullet}}_{k})^{2}\varepsilon_{k}^{2}\leq
25(2Q_{k}U_{k})^{2}\varepsilon_{k}^{2}\leq
32\varepsilon_{k}^{1.6}/(R_{0})^{2}\leq\varepsilon_{k}^{1.5}$

hence

(9.8) $\varepsilon_{k}\leq\varepsilon^{1.5^{k-1}}.$

From here, it is easy to see that $\varepsilon^{\prime\prime}_{k}$ also
converges to 0 with similar speed.

######  Example 9.1.

Let us choose for some $c\geq 1$

(9.9) $\displaystyle{T_{\bullet}}_{1}$ $\displaystyle=1,$
$\displaystyle{T^{\bullet}}_{1}$ $\displaystyle=2,$ $\displaystyle Q_{k}$
$\displaystyle=c^{2}k^{2},$ $\displaystyle U_{k}$ $\displaystyle=c^{3}k^{4},$
$\displaystyle{\text{Cap\/}}_{k}$ $\displaystyle=c(\log k\vee 1).$

Conditions (9.3) and (9.5) are satisfied for large $c$.

There is a slightly better bound on $\varepsilon_{k}$ here than in (9.8).

(9.10) $\varepsilon_{k+1}\leq
25(2Q_{k}U_{k})^{2}\varepsilon_{k}^{2}=32c^{10}k^{12}\varepsilon_{k}^{2}.$

Let us prove, by induction, for small enough $\varepsilon$,

(9.11) $\varepsilon_{k}\leq\varepsilon^{2^{k-2}+(k+1)/4}.$

For $k=1$, the statement gives $\varepsilon\leq\varepsilon$. For $k>1$, using
(9.10) and the inductive assumption,

$\varepsilon_{k+1}\leq\varepsilon^{2^{k-1}+(k+1)/2}32c^{10}k^{12}=\varepsilon^{2^{k-1}+(k+2)/4}(32\varepsilon^{k/4}c^{10}k^{12}).$

For small enough $\varepsilon$, the last factor is less than 1. ∎

####  9.1.3. Amplifier frames

The above definitions must be modified for the notion of an amplifier frame,
(not needed for the basic non-ergodicity result). An amplifier frame Frame is
given by the same sequences as a broadcast amplifier frame, and some
additional sequences

$q_{k},{w}_{k},{\text{Rd\\_trans\/}}_{k}(),{\text{Output\/}}^{k},R_{1}(k).$

Here, ${\text{Rd\\_trans\/}}_{k}()$ describes a rider transition function with
bandwidth $\leq{w}_{k}$, the field ${\text{Rider\/}}^{k}$ has subfield
${\text{Output\/}}^{k}$ on which this function has monotonic output, and the
number $R_{1}(k)$ is a redundancy coefficient. Each cell will have space

$B^{\prime}_{k}=\prod_{i<k}q_{i}$

for the represented information. An object Frame given by the above
ingredients is an amplifier frame if the conditions listed below hold.

Complexity Upper Bounds:

The sequence ${\text{Rd\\_trans\/}}_{k}^{({w}_{k})}()$ of functions (see
(2.5)) and all other parameters in Frame are uniform sequences with complexity
coefficient $R_{0}$;

Bandwidth Lower Bound:

We should be able to deal with numbers comparable to the size of the colony
and the work period within the time and space bound ${w}_{k}$:

(9.12) ${w}_{k}\geq\log U_{k};$

Redundancy Lower Bound:

The redundancy must help duplicate the content of at least a certain constant
number of cells:

(9.13) $R_{1}(k)\geq R_{0}/Q_{k}.$

Capacity Lower Bounds:

The capacity ${\text{Cap\/}}_{k}$ of a cell should accomodate all the original
information $2B^{\prime}_{k}$ (2 bits per primitive cell).

(9.14) $2B^{\prime}_{k}\leq{\text{Cap\/}}_{k}.$

The colony must represent the state of the big cell with redundancy. It also
needs extra space for computing with a few bandwidths of information of the
big cell.

(9.15) $(1+R_{1}(k)){\text{Cap\/}}_{k+1}+R_{0}{w}_{k+1}\leq
Q_{k}{\text{Cap\/}}_{k}.$

Work Period Lower Bound:

There must be enough dwell periods in a work period to perform the necessary
computations of a simulation:

(9.16) $U_{k}\geq R_{0}Q_{k}(\frac{{\text{Cap\/}}_{k}}{{w}_{k}}+\log
Q_{k}+\log k)$

It costs $Q{\text{Cap\/}}_{k}/{w}_{k}$ to perform $Q$ steps of simulated
computation of Univ when each track of size ${w}_{k}$ must be worked
separately. The other terms in the parentheses are typically of lower order
and are needed only for technical reasons, in the proof of self-organization.

Error upper bound, Time stability:

These conditions are the same as the ones for broadcast amplifier frames.

The inequality (9.15) has the following consequences, similar to (4.32):

######  Lemma 9.2.

$\displaystyle\sum_{k}R_{1}(k)\frac{{\text{Cap\/}}_{k+1}}{B_{k+1}}<\infty,$
$\displaystyle\sum_{k}\frac{{w}_{k+1}}{B_{k+1}}<\infty.$

Thus, as expected, if we have constant space redundancy, i.e.
${\text{Cap\/}}_{k+1}/B_{k+1}$ is bounded away from 0 then
$\sum_{k}R_{1}(k)<\infty$, i.e. the redundancies of each level form a
converging series. This will then impose, via (9.16), a lower bound on the
time redundancy achievable by these amplifiers.

###### Proof.

Inequality (9.15) can be rearranged as

(9.17)
$R_{1}(k)\frac{{\text{Cap\/}}_{k+1}}{B_{k+1}}+R_{0}\frac{{w}_{k+1}}{B_{k+1}}\leq\frac{{\text{Cap\/}}_{k}}{B_{k}}-\frac{{\text{Cap\/}}_{k+1}}{B_{k+1}}.$

∎

Let us remind the reader that the constructions involving the Rider and Guard
fields are not needed for the simple non-ergodicity results.

######  Example 9.3.

Let us choose for some $c\geq 1$

(9.18) $\displaystyle{T_{\bullet}}_{1}$ $\displaystyle=1,$
$\displaystyle{T^{\bullet}}_{1}$ $\displaystyle=2,$ $\displaystyle Q_{k}$
$\displaystyle=c^{2}k^{2},$ $\displaystyle q_{k}$ $\displaystyle=Q_{k},$
$\displaystyle R_{1}(k)$ $\displaystyle=c/Q_{k}=1/(ck^{2}),$ $\displaystyle
U_{k}$ $\displaystyle=c^{3}k^{4}=cQ_{k}/R_{1}(k),$ $\displaystyle{w}_{k}$
$\displaystyle=R_{1}(k)B_{k},$ $\displaystyle{\text{Cap\/}}_{k}$
$\displaystyle=2B_{k}(1+1/k).$

The transition function ${\text{Rd\\_trans\/}}_{k}$ will be the aggregated
function ${\text{Tr\/}}_{{\text{Univ\/}}}^{{w}_{k}}$ as defined in Example
3.4. This satisfies the required complexity bounds. Conditions (9.12) and
(9.13) are satisfied with large $c$. Condition (9.14) is satisfied by the
definition of ${\text{Cap\/}}_{k}$. It is easy to check that (9.15) also holds
with large $c$. Condition (9.16) will be satisfied with large $c$. The error
upper bound is satisfied just as for the broadcast amplifier example, and we
have (9.11) again.

The parameters of this example are chosen for constant space redundancy, at
the price of time redundancy that comes as an extra factor of
${\text{Cap\/}}_{k}/{w}_{k}$ at every level.

For later reference, here is an explicit expression falling between
${T_{\bullet}}_{k}$ and ${T^{\bullet}}_{k}$:

(9.19) $\prod_{i<k}U_{i}=c^{3(k-1)}((k-1)!)^{4}=e^{4k\log k+O(k)}.$

The expression for $B_{k}$ is similar. ∎

###  9.2. The existence of amplifiers

We give a separate, simpler track of definitions for broadcast amplifiers. A
(uniform) broadcast amplifier is given by a broadcast amplifier frame Frame,
uniform sequences $({\text{Sim\\_trans\/}}_{k})$, $(M_{k},\Phi_{k})_{k\geq 1}$
with $\Phi_{k}=(\Phi_{k}^{*},\varphi_{k*})$ as defined in Subsection 3.6 and a
uniform sequence of codes $\varphi_{k**}$ with a sequence of fields
$({\text{F\/}}^{k})$ such that

  1. (a)

(9.20)
$M_{k}={\text{Rob\/}}({\text{Tr\/}}_{k},B_{k},{T_{\bullet}}_{k},{T^{\bullet}}_{k},\varepsilon_{k},\varepsilon^{\prime}_{k});$

  2. (b)

$({\text{F\/}}^{k})$ forms a broadcast field for both $(\varphi_{k*})$ and
$(\varphi_{k**})$, as defined in Subsection 4.2;

  3. (c)

Simulation $\Phi_{k}$ has $\varepsilon^{\prime\prime}_{k}$-error-correction
for $\varphi_{k**}$;

  4. (d)

The damage map of the simulation $\Phi_{k}$ is defined as in Subsection 8.1.

(The last condition explains the definition of $\varepsilon_{k+1}$.) With
Lemma 8.4, it will imply the Restoration Property for the simulated
trajectory.

The following definition is not needed for the simple non-ergodicity result: A
(uniform) amplifier is given by an amplifier frame Frame, uniform sequences
$({\text{Sim\\_trans\/}}_{k})$, $({\text{Rider\/}}^{k})$,
$({\text{Guard\/}}^{k})$, a hierarchical code

(9.21)
$\Psi=(\SS_{k},Q_{k},\varphi_{k*},{\text{Rider\/}}^{k},q_{k},\gamma_{k},a_{k})_{k\geq
1}$

as in 4.13 and an amplifier $(M_{k},\Phi_{k})_{k\geq 0}$ where
$\Phi_{k}=(\Phi_{k}^{*},\varphi_{k*})$ is defined as in Subsection 3.6, and a
sequence of codes $\varphi_{k**}$ and fields ${\text{Guard\/}}^{k}$ such that

  1. (a)

$({\text{Rider\/}}^{k})$, and $({\text{Guard\/}}^{k})$ form a guarded shared
field for $(\varphi_{k*})$, $(\varphi_{k**})$, as defined in Subsection 4.2;

  2. (b)

the damage map of the simulation $\Phi_{k}$ is defined as in Subsection 8.1;

  3. (c)

${\text{Tr\/}}_{k}$ is combined from ${\text{Rd\\_trans\/}}_{k}$ and
${\text{Sim\\_trans\/}}_{k}$, with fields ${\text{Rider\/}}^{k}$,
${\text{Guard\/}}^{k}$;

  4. (d)

$M_{k}$ is as in (9.20);

  5. (e)

$\Phi_{k}$ has $\varepsilon^{\prime\prime}_{k}$-error-correction for
$\varphi_{k**}$;

Most of our effort will be devoted to proving the following lemma.

######  Lemma 9.4 (Amplifier).

Every (broadcast) amplifier frame Frame with large enough $R_{0}$ can be
completed to a uniform (broadcast) amplifier.

###  9.3. The application of amplifiers

###### Proof of Lemma 3.7.

We will actually prove the more general variable-period variant of the lemma,
with $T_{k}={T_{\bullet}}_{k}$.

Let us define a broadcast amplifier frame Frame e.g. as in Example 9.1.
Applying the Amplifier Lemma in the broadcast case, we obtain a broadcast
amplifier with media $M_{k}$ as in (9.20) with a hierarchical code having a
broadcast field $({\text{F\/}}^{k})$ for both $(\varphi_{k*})$ and
$(\varphi_{k**})$. Let us denote the whole system of code and the broadcast
field (with the additional mappings $\gamma_{k}$) by $\Psi$ as in (4.11). For
any value $u_{1}$ of the field ${\text{F\/}}^{1}$, we create an initial
configuration $\eta^{1}(\cdot,0)=\Gamma(u_{1};\Psi)$ as in (4.12).

Then all properties but the initial stability property of an abstract
amplifier (defined in Lemma 3.7) are satisfied by definition. For the initial
stability property it is sufficient to note that each medium $M_{k}$ is a
robust medium, with work period lower bound ${T_{\bullet}}_{k}$. Therefore, if
$\eta^{k}$ is a trajectory of $M_{k}$ and $t<{T_{\bullet}}_{k}$ then for each
$x$ the probability that $\eta^{k}(x,t)\neq\eta^{k}(x,0)$ is less than the
probability that damage occurs in $\\{x\\}\times[0,{T_{\bullet}}_{k}]$. This
can be bounded by the Restoration Property. ∎

###### Proof of Theorem 6.14.

This proof starts analogously to the proof of Lemma 3.7.

Let us define an amplifier frame Frame as in Example 9.3, with the rider
transition function having the property

${\text{Rd\\_trans\/}}_{k}({\mathbf{r}})=r_{0},$

i.e leaving all fields (in particular, the rider and guard fields) unchanged.
Applying the Amplifier Lemma, we obtain a uniform amplifier with media $M_{k}$
as in (9.20) with a hierarchical code having a guarded shared field
${\text{Rider\/}}^{k}$ with guard field ${\text{Guard\/}}^{k}$ as in (9.21).
Let $K$ be largest with $B_{K}\leq N$. For any infinite configuration