Tel Aviv University<EMAIL_ADDRESS>Tel Aviv University,
<EMAIL_ADDRESS>Y. Nakar and D. Ron [500]Theory of computation
Streaming, sublinear and near linear time algorithms John Q. Open and Joan R.
Access 2 42nd Conference on Very Important Topics (CVIT 2016) CVIT 2016 CVIT
2016 December 24–27, 2016 Little Whinging, United Kingdom 42 23

# Testing Dynamic Environments: Back to Basics

Yonatan Nakar  Dana Ron

###### Abstract

We continue the line of work initiated by Goldreich and Ron (Journal of the
ACM, 2017) on testing dynamic environments and propose to pursue a systematic
study of the complexity of testing basic dynamic environments and local rules.
As a first step, in this work we focus on dynamic environments that correspond
to elementary cellular automata that evolve according to threshold rules.

Our main result is the identification of a set of conditions on local rules,
and a meta-algorithm that tests evolution according to local rules that
satisfy the conditions. The meta-algorithm has query complexity
$\text{poly}(1/{\epsilon})$, is non-adaptive and has one-sided error. We show
that all the threshold rules satisfy the set of conditions, and therefore are
$\text{poly}(1/{\epsilon})$-testable. We believe that this is a rich area of
research and suggest a variety of open problems and natural research
directions that may extend and expand our results.

###### keywords:

Property Testing

###### category:

##  1 Introduction

Property testing [12, 5] is the study of algorithms that distinguish between
objects that have a given property and those that are far from having the
property, by performing a small number of queries to the object. Goldreich and
Ron [6] initiated the study of testing _dynamic environments_ , which
introduces a temporal aspect to property testing. In this context, the entity
being tested changes with time, and is referred to as an _environment_.

Starting from some initial _configuration_ (say, a vector or a matrix), the
environment is supposed to evolve according to a prespecified _local_ rule.
The rule is local in the sense that the value associated with each location in
the environment at time $t$ is determined by the values of nearby locations at
time $t-1$. The goal of the testing algorithm is then to distinguish between
the case that the environment indeed evolves according to the rule, and the
case in which the evolution significantly strays from obeying the rule. To
this end, the algorithm can query the value of any location of the environment
at any of the available time steps, as long as it does not “go back in time”.
Namely, the algorithm cannot choose to query a location at time $t$ after it
has queried some location at time $t^{\prime}>t$. We refer to this as the
_time-conforming_ requirement. The aim is to design time-conforming algorithms
with low query complexity.

Goldreich and Ron [6] investigate the complexity landscape of testing dynamic
environments from multiple angles. From a hardness perspective, they show that
there are dynamic environments whose testing requires high query complexity
and running time, and that adaptivity and time-conformity are relevant
constraints which can significantly impact the query complexity. However, as
we discuss in Section 1.4, relatively little is known regarding positive
results for testing specific rules.

In our quest for understanding which natural families of dynamic environments
can be tested efficiently, we propose to first “go back to the basics” and
study testing in the simplest of dynamic environments. Namely, in this work we
consider environments defined by one-dimensional configurations, which evolve
according to local rules that are functions of the current location and its
two immediate neighbors. These dynamic environments, originally introduced by
von Neumann [13], have been extensively studied under the name of _Elementary
Cellular Automata_ [14] (see definition in Section 1.1). While these
environments can be described in simple terms, they are nevertheless able to
capture complex behavior.111Some rules are even Turing complete [4]. Cellular
automata have played a role in various research fields and applications.
Examples include modeling physical [2] and chemical [7] systems, VLSI design
[3], music generation [1], analyzing plant population dynamics [15], forest
fire spread [17], city traffic [11], urban sprawl [8], and more.

As we discuss in Section 1.4, there are several hardness results (both
regarding the query complexity and the running time) for testing dynamic
environments that correspond to one-dimensional cellular automata (over non-
binary alphabets) [6]. Hence, in order to obtain efficient algorithms, it is
necessary to restrict the rules considered. In the current work, our main
focus is on perhaps the most basic and natural rules, defined by threshold
functions. Such functions have received much attention within the study of
propagation of information/influence in networks (see, e.g., the review paper
of Peleg [10], and the recent Ph.D. thesis of Zehmakan [16] and references
within).

Our testers are based on a general meta-algorithm which works for rules that
satisfy a set of conditions that we define. In essence, the conditions capture
a certain type of behavior leading to ultimate convergence. This behavior
induces a global structure on the environment which we exploit in our meta-
algorithm.

We hope this work can serve as a basis for further extensions and
generalizations, some of which we discuss shortly in Section 1.5.

###  1.1 Testing basic evolution rules

We now formally define the problems we study. We use $[m]$ to denote the set
$\left\\{0,...,m-1\right\\}$. For two integers $n$ and $m$, let ${\tt
ENV}:[m]\times{\mathbb{Z}_{n}}\to\\{0,1\\}$ denote the evolving environment,
and for any $t\in[m]$ let ${\tt ENV}_{t}:{\mathbb{Z}_{n}}\to\\{0,1\\}$ (the
environment at time $t$) be defined by ${\tt ENV}_{t}(i)={\tt ENV}(t,i)$. In
general, we refer to a function $\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$ as a
_configuration_. When convenient, we may view $\sigma$ as a (cyclic) binary
string of length $n$.

For a function (evolution rule) $\rho:\\{0,1\\}^{3}\to\\{0,1\\}$, we say that
${\tt ENV}$ _evolves according to $\rho$_, if for every $i\in{\mathbb{Z}_{n}}$
and $t>0$, we have that ${\tt ENV}_{t}(i)=\rho({\tt ENV}_{t-1}(i-1),{\tt
ENV}_{t-1}(i),{\tt ENV}_{t-1}(i+1))$, where all operations are modulo $n$. We
use $\mathcal{E}^{\rho}_{m,n}$ to denote the set of environments ${{\tt
ENV}:[m]\times{\mathbb{Z}_{n}}\to\\{0,1\\}}$ that evolve according to $\rho$.
As in [6], we employ the standard notion of distance used in property testing
and say that ${\tt ENV}:[m]\times{\mathbb{Z}_{n}}\to\\{0,1\\}$ is
_${\epsilon}$ -far from evolving according to $\rho$_ (${\epsilon}$-far from
$\mathcal{E}^{\rho}_{m,n}$) if $|\\{(t,i):{\tt ENV}(t,i)\neq{\tt
ENV}^{\prime}(t,i)\\}|>{\epsilon}mn$ for every ${\tt
ENV}^{\prime}\in\mathcal{E}^{\rho}_{m,n}$.222In the context of dynamic
environments, this notion of distance can be interpreted as capturing
“measurement errors” due to some noise process. Namely, it can be viewed as
allowing the testing algorithm to accept not only “perfect” environments, but
also environments that correspond to a correct evolution with a bounded
fraction of corruptions. Also note that being ${\epsilon}$-far from evolving
according to $\rho$ does not simply translate to there being an
${\epsilon}$-fraction of pairs $(t,i)$ for which ${\tt
ENV}_{t}(i)\neq\rho({\tt ENV}_{t-1}(i-1),{\tt ENV}_{t-1}(i),{\tt
ENV}_{t-1}(i+1))$ (which would be trivial to test).

Given $n$, $m$, and a distance parameter ${\epsilon}\in(0,1)$, a testing
algorithm for evolution according to a rule $\rho$ should distinguish with
constant success probability between the case that an environment ${\tt ENV}$
belongs to $\mathcal{E}^{\rho}_{m,n}$ and the case that it is ${\epsilon}$-far
from $\mathcal{E}^{\rho}_{m,n}$. To this end, the algorithm is given query
access to ${\tt ENV}$, where a query on a pair $(t,i)$ cannot follow any query
on $(t^{\prime},i^{\prime})$ for $t^{\prime}>t$. We are interested in bounding
both the total number of queries performed by the algorithm (as a function of
${\epsilon}$, and possibly $m$ and $n$) and the maximum number of queries it
performs at any time step (which we refer to as its _temporal query
complexity_).

###  1.2 Our results

We identify several conditions on local rules (which are formally stated in
Section 3), such that if a rule $\rho$ satisfies these conditions, then
evolution according to $\rho$ can be tested with query complexity
$\text{poly}(1/{\epsilon})$ with one-sided error. Our testers have the
advantage that they are non-adaptive, and therefore, in particular, time-
conforming.

######  Theorem 1.1.

Let $\Psi$ be the set of conditions specified in Section 3. For every rule
$\rho$ that satisfies the conditions in $\Psi$, it is possible to test
evolution according to $\rho$ by performing $O(1/{\epsilon}^{4})$ queries.
Furthermore, the testing algorithm is non-adaptive and has one-sided error.

To establish Theorem 1.1, we present a _meta-algorithm_ for testing evolution
and prove its correctness for rules that satisfy the aforementioned conditions
(the set $\Psi$). It is a meta-algorithm in the sense that it is based on
certain subroutines that are rule-specific (but have a common functionality of
detecting violations of evolution according to the tested rule). We provide a
high-level discussion of the conditions and the algorithm in Section 1.3.

Our main application of the meta-algorithm is to the natural family of
threshold rules.

######  Definition 1.2.

We say that a rule $\rho:\\{0,1\\}^{3}\to\\{0,1\\}$ is a _threshold_ rule if
there exist a threshold integer $0\leq b\leq 3$ and a bit
$\alpha\in\left\\{0,1\right\\}$ such that
$\rho(\beta_{1},\beta_{2},\beta_{3})=\alpha$ if and only if
$\beta_{1}+\beta_{2}+\beta_{3}\geq b$.

We prove:

######  Theorem 1.2.

For each threshold rule $\rho$, evolution according to $\rho$ can be tested
with query complexity $O(1/{\epsilon}^{4})$. Furthermore, the testing
algorithm is non-adaptive and has one-sided error.

We also show that the conditions hold for two additional (non-threshold)
rules, so the applicability of our meta-algorithm is more general (Section
10). We believe that appropriate (perhaps more complex) variants of our
algorithm can be used to test an even larger variety of basic local rules (see
Section 1.5), where we conjecture that this is true for all rules that
ultimately converge. Interestingly, while the two additional rules are not
threshold rules as per Definition 1.2, they can be represented as weighted
threshold rules (which are a subclass of ultimately converging rules).

###  1.3 The high-level ideas behind our results

In this high-level discussion, we assume for simplicity that $m\geq n$ (the
case $m<n$ can be essentially reduced to this case).

####  1.3.1 Convergence, final/non-final locations and prediction functions

To give an intuition on the convergence behavior that our conditions capture,
it is useful to first discuss the notion of _ultimate convergence_. A rule
$\rho$ ultimately converges if, for any initial configuration ${\tt ENV}_{0}$,
an environment evolving according to $\rho$ converges after a bounded number
of steps to either a single final configuration or to a constant number of
configurations between which it alternates. For example, consider the majority
rule (threshold $2$). Unless the initial configuration is $(01)^{n/2}$, the
environment ultimately converges to some configuration that consists of blocks
of $0$s and $1$s of size at least 2 each (and if it is $(01)^{n/2}$, then it
alternates between $(01)^{n/2}$ and $(10)^{n/2}$).

Once an environment converges, testing is straightforward since we can easily
predict the values of locations in future time steps and then verify that
indeed they hold the predicted values (or else we reject). The issue, however,
is that convergence is not ensured to be reached after a small number of time
steps.333In fact, there are initial configurations that require $\Omega(n)$
steps before they ultimately converge. In other words, knowing that a rule
ultimately converges cannot be exploited directly. Hence, the challenge is to
identify and formalize conditions that allow for “pre-convergence prediction”.
Namely, conditions that imply the ability to predict future values of
locations based on the current values of these and other locations (before
convergence is reached).

In this context, our conditions try to formalize the idea that rules exhibit a
certain _local_ convergence, which “expands” with time. The first ingredient
of our approach is the observation that, in the case of the majority rule, if
at any time step $t$, ${\tt ENV}_{t}(i)\in\\{{\tt ENV}_{t}(i-1),{\tt
ENV}_{t}(i+1)\\}$ , then ${\tt ENV}_{t^{\prime}}(i)={\tt ENV}_{t}(i)$ for any
$t^{\prime}>t$ (operations are modulo $n$). We say in such a case that
location $i$ is _final_ at time $t$ (in ${\tt ENV}$). Otherwise it is _non-
final_. Crucially for us, whether a location $i$ is final or not at a certain
time step depends solely on its local neighborhood at that time (and can hence
be verified with a constant number of queries).

An important property of a location being final at time $t$ (in addition to
converging to their final value, up to alternations), is the aforementioned
expansion (or “transmission of finality”). Namely, a location $i$ that is non-
final at time $t$ becomes final at time $t+1$ if either $i-1$ or $i+1$ is
final at time $t$ (possibly both). Furthermore, it cannot become final if both
its neighbors are non-final. Another related property of final locations is
that (under certain circumstances), they can be used to predict the values of
locations that become final in the future, based on a (rule-specific)
_prediction function_. A similar statement holds for non-final locations
(though the circumstances are different).

####  1.3.2 The meta-algorithm: the grid and violating pairs

Based on these properties (which are formalized in the conditions we
introduce), our (meta) algorithm works in two stages. In the first stage, it
queries the environment at time $t_{1}=\Theta({\epsilon}m)$ on
$O(1/{\epsilon}^{2})$ equally spaced locations, which we refer to as _the grid
locations_ , and their local neighborhoods. This allows the algorithm to
determine which of the grid locations are final at time $t_{1}$ and which are
non-final. If the answers it gets are not consistent with any environment that
evolves according to $\rho$ (in which case we say that the grid is _not
feasible_), then it rejects.

In its second stage, the algorithm uniformly samples $O(1/{\epsilon})$ random
time-location pairs $(t,i)$ and queries ${\tt ENV}_{t}$ on $i$ and its local
neighborhood. It then checks whether the answers are consistent with the
answers to queries in the first stage (on the grid locations and their
neighborhoods) or constitute a _violation_. The definition of
consistency/violation is based on the aforementioned prediction functions of
the tested rule.

One may have hoped that such a consistency check is sufficient, in the sense
that all (or almost all) pairs $(t,i)$ can be predicted based on the answers
to the queried grid locations. Unfortunately, this is not the case. There are
(possibly many) pairs $(t,i)$ whose $0/1$ values are not determined given the
first-stage answers. However, we show that such pairs are constrained in a
different way (in environments that evolve according to $\rho$): their
location must have become final by time $t_{2}=t_{1}+\Delta$, where $\Delta$
is the distance between grid location. Hence, for each selected pair $(t,i)$,
the algorithm also queries ${\tt ENV}_{t_{2}}$ on location $i$ (and its
neighborhood) and checks consistency with the queried locations at time
$t_{2}$.

####  1.3.3 On the analysis of the algorithm and “backward prediction”

To show that the algorithm always accepts environments that evolve according
to the tested rule $\rho$, we prove that our definition of violation is such
that there are no violations in such environments (assuming $\rho$ satisfies
the aforementioned conditions). The more involved part of the analysis is
proving that if the environment ${\tt ENV}$ is ${\epsilon}$-far from evolving
according to $\rho$, then the algorithm will detect this with probability at
least $2/3$. To this end, we prove the contrapositive statement. Namely, we
show that if the algorithm accepts with probability at least $2/3$, then there
exists an environment that evolves according to $\rho$ and is
${\epsilon}$-close to ${\tt ENV}$. This is done by showing that we can
construct an initial configuration ${\tt ENV}^{\prime}_{0}$, such that if we
let it evolve according to $\rho$, resulting in an environment ${\tt
ENV}^{\prime}\in\mathcal{E}^{\rho}_{m,n}$, then we can upper bound the number
of pairs $(t,i)$ such that ${\tt ENV}_{t}(i)\neq{\tt ENV}^{\prime}_{t}(i)$ by
${\epsilon}mn$.

Here we build on a useful property of the prediction functions, by which they
allow us a certain “prediction back in time”. Namely (for $t_{1}$ and $t_{2}$
as mentioned above), we use the queried grid locations at time $t_{1}$ as well
as some locations at time $t_{2}$ (which have not been queried) to determine
values of locations at the earlier time $0$ in ${\tt ENV}^{\prime}$. We prove
that this can be done in a way that ensures that ${\tt ENV}^{\prime}$ agrees
with ${\tt ENV}$ on all pairs $(t,i)$ that are not violating.

###  1.4 A short overview of the results in [6]

As stated earlier, the study of testing dynamic environments was initiated by
Goldreich and Ron [6], who present several general results as well as analyze
two natural specific rules. We first provide a short overview of their main
general results.

They prove that the query complexity of testing (one-dimensional) rules may
have high query complexity. Specifically, they show that there exists a
constant $c>0$ and an evolution rule $\rho:\Sigma^{3}\to\Sigma$ such that any
tester of evolution according to $\rho$ requires $\Omega(n^{c})$
queries.444Observe that it is possible to test the evolution according to any
rule $\rho$ over configurations of size $n$ by performing $O(n+1/{\epsilon})$
queries ($n$ queries to the initial configuration and $O(1/{\epsilon})$
uniformly selected queries elsewhere). To get sublinear temporal query
complexity, a total of $O(n/{\epsilon})$ uniformly selected queries suffice
(by applying a simple union bound over all possible initial configurations).
They also prove that testing dynamic environments may be NP-Hard, provided
that the temporal query complexity is “significantly sublinear” (where $f(x)$
is significantly sublinear if $f(x)<x^{1-\Omega(1)}$). More precisely, they
show that for every constant $c>0$ there exists an evolution rule
$\rho:\Sigma^{3}\to\Sigma$ such that no (time-conforming) polynomial-time
testing algorithm with temporal query complexity $n^{1-c}$ can test whether
$n$-sized environments evolve according to $\rho$ (assuming
$\mathcal{NP}\not\subseteq\mathcal{BPP}$). Their general results also include
a theorem concerning the usefulness of adaptivity in testing dynamic
environments, a study of the relation between testing and learning dynamic
environments, and a result on the power of being non time-conforming.

Goldreich and Ron [6] also provide testers for evolution according to two
specific (classes of) rules. The first is the class of linear rules, which in
the binary 1-dimensional case corresponds to the XOR rule in elementary
cellular automata. They show that for any $d\geq 1$ and any field $\Sigma$ of
prime order, there exists a constant $\gamma<d$ such that the following holds.
For any linear rule $\rho:\Sigma^{3^{d}}\rightarrow\Sigma$ there exists a
time-conforming oracle machine of (total) time complexity
$\text{poly}(1/{\epsilon})\cdot n^{\gamma}$ that tests the consistency of an
evolving environment with respect to $\rho$. Furthermore, the tester is non-
adaptive and has one-sided error.

Their second specific positive result, loosely stated, captures fixed-speed
movement of objects in one-dimension such that colliding objects stop forever.
They present a (time-conforming) algorithm of (total) time complexity
poly($1/{\epsilon}$) that tests the consistency of evolving environments with
respect to that rule.

###  1.5 Future directions

###### Basic dynamic environments.

A natural question that arises is whether a more nuanced version of the set of
conditions formalized in this paper and the meta-algorithm can be defined and
proved to work for other rules in the realm of basic dynamic environments.
Indeed, preliminary results suggest that several other rules that ultimately
converge exhibit behaviors that “resemble” the ones captured by our
conditions. This leads us to the following conjecture.

Conjecture. If a rule $\rho$ ultimately converges, then it is
poly($\frac{1}{\epsilon}$)-testable.

While our meta-algorithm does not apply to rules that do not ultimately
converge, there are natural rules that fall under this category (the XOR rule
for instance). This raises the question of whether $\text{poly}(1/{\epsilon})$
testers exist for such rules. The answer is that there are
$\text{poly}(1/{\epsilon})$-testable rules that do not ultimately converge,
but as we’ll see, the question should be slightly rephrased.555We thank one of
the anonymous reviewers of this paper for pointing this out. To give one
example, for the rule $\rho$ defined as $\rho(x,y,z)=x$, each configuration is
simply a copy of the previous configuration, shifted one location to the
right. That is, while an environment evolving according to this rule does not,
technically, ultimately converge, this rule is trivially
$\text{poly}(1/{\epsilon})$-testable. However, this particular rule (and other
rules that are capable of producing such “shifting behaviors”) also has the
property of not being symmetric (i.e., it does not hold that
$\rho(x,y,z)=\rho(z,y,x)$ for every $x,y,z$). Hence, one way to rephrase the
question is restricting it to symmetric rules.

######  Open Problem 1.

Are there any symmetric rules that do not ultimately converge and are
$\text{poly}(1/{\epsilon})$-testable?

Another way to rephrase this question is to define a more general notion of
ultimate convergence. Specifically, we say that a rule $\rho$ ultimately
converges up to a shift if, for any initial configuration ${\tt ENV}_{0}$, an
environment evolving according to $\rho$ converges after a bounded number of
steps to a constant number of configuration equivalence classes between which
it alternates, where two configurations are equivalent if they are equal up to
a shift.

######  Open Problem 2.

Are there any non-symmetric rules that do not ultimately converge up to a
shift and are $\text{poly}(1/{\epsilon})$-testable?

As mentioned in Section 1.4, it has been shown in [6] that the XOR rule is
sublinearly testable. However, the query complexity of the tester depends on
the size of the environment and is only mildly sublinear (the complexity is
$O(n^{0.8})$ for an environment of size $n$). This raises the question of
whether there exists a tester for the XOR rule with significantly lower query
complexity (maybe even polylogarithmic). Another question that can be raised
is whether there are other symmetric rules, ones that do not ultimately
converge, that can be tested with a sublinear query complexity that depends on
the size of the environment.

######  Open Problem 3.

Which symmetric rules that do not ultimately converge can be tested with query
complexity that is sublinear in (but strictly grows with) the size of the
environment?

###### More general dynamic environments.

Building on the ideas for testing basic dynamic environments, it may be
possible to venture into more general environments. One such generalization is
to consider rules that depend on more than just the three locations
constituting the immediate neighborhood. Other generalizations are to
environments and rules over non-binary values, higher dimensions, and
environments that evolve on more general graphs.

###### Non-deterministic rules.

We also suggest considering local rules that are non-deterministic in the
sense that given some configuration, the rule allows several configurations to
follow. An example of one such rule, which can be thought of as a relaxation
of the OR rule, is the rule in which each value is restricted to be
monotonically non-decreasing with respect to the previous values at the
location’s neighborhood.

##  2 Preliminaries

In addition to the basic definitions provided in Section 1.1 regarding testing
dynamic environments, here we introduce several more definitions and
notations.

In all that follows, when performing operations on locations
$i\in{\mathbb{Z}_{n}}$, these operations are modulo $n$. For a pair of
locations $i,j\in{\mathbb{Z}_{n}}$ we use $[i,j]$ to denote the sequence
$i,i+1,\dots,j$ (so that it is possible that $j<i$).

######  Definition 2.1.

For a location $i\in{\mathbb{Z}_{n}}$ and an integer $r$, the $r$-neighborhood
of $i$, denoted $\Gamma_{r}(i)$, is the sequence $[i-r,i+r]$. For a set of
locations $I\subseteq{\mathbb{Z}_{n}}$, we let $\Gamma_{r}(I)$ denote the set
of locations in the union of sequences $[i-r,i+r]$ taken over all $i\in I$.

######  Definition 2.2.

For an integer $n$ and a local rule $\rho$, let ${\mathcal{M}}_{\rho}(n)$
denote the (deterministic) state machine that is defined as following. Each
state of ${\mathcal{M}}_{\rho}(n)$ corresponds to a different configuration
$\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$. If a state corresponds to a
configuration $\sigma$, then it has a single transition going to the state
corresponding to the configuration that results from applying $\rho$ to
$\sigma$.

The period of ${\mathcal{M}}_{\rho}(n)$, denoted $p_{\rho}(n)$, is the longest
size of a (directed) cycle in ${\mathcal{M}}_{\rho}(n)$. If there exists a
constant $p$ such that $p_{\rho}(n)=p$ ($p_{\rho}(n)\leq p$) for every
sufficiently large $n$, then we say that $\rho$ has period (at most) $p$, and
that $\rho$ ultimately converges.

Observe that for every ${\mathcal{M}}_{\rho}(n)$, each strongly connected
component in ${\mathcal{M}}_{\rho}(n)$ is either a single state with no edges
in the component or a cycle (where in particular, the cycle may be a self-
loop). For example, if $\rho$ is the OR function, then it has period $1$ (as
it contains only two cycles: one is a self-loop for the state corresponding to
the configuration $1^{n}$ and the other is a self loop for the state
corresponding to the configuration $0^{n}$). On the other hand, there are
rules, such as XOR, for which $p_{\rho}(n)=\Omega(n)$.

######  Definition 2.3.

For two locations $i,i^{\prime}\in{\mathbb{Z}_{n}}$, we let
$\overrightarrow{\rm dist}(i,i^{\prime})=i^{\prime}-i$ denote the directed
distance from $i$ to $i$, and let ${\rm
dist}(i,i^{\prime})=\min\\{\overrightarrow{\rm
dist}(i,i^{\prime}),\overrightarrow{\rm dist}(i^{\prime},i)\\}$ denote the
(undirected) distance.

Note that since operations on locations are modulo $n$, we have that
$\overrightarrow{\rm dist}(i,i^{\prime})\leq n-1$, while ${\rm
dist}(i,i^{\prime})\leq n/2$ for all $i,i^{\prime}\in{\mathbb{Z}_{n}}$.

######  Definition 2.4.

For $t\in[m]$ and $i\in{\mathbb{Z}_{n}}$, we refer to $(t,i)$ as a time-
location pair (or simply pair).

Given two locations, $i,i^{\prime}\in{\mathbb{Z}_{n}}$ and two time steps
$t,t^{\prime}\in[m]$ where $t>t^{\prime}$, we say that the pair $(t,i)$
descends from the pair $(t^{\prime},i^{\prime})$ if ${\rm
dist}(i,i^{\prime})\leq t-t^{\prime}$. We say that $(t,i)$ is a descendant of
$(t^{\prime},i^{\prime})$ and that $(t^{\prime},i^{\prime})$ is an ancestor of
$(t,i)$.

######  Definition 2.5.

For an integer $r$, an $r$-pattern is a string in $\\{0,1\\}^{r}$.

##  3 The Conditions

Let $\rho:\\{0,1\\}^{3}\to\\{0,1\\}$ be a local rule. We present several
conditions, such that if they all hold, then the rule $\rho$ can be tested
with $\text{poly}(1/{\epsilon})$ queries. These conditions capture properties
of local rules that can be exploited by our (meta) algorithm.

The conditions are defined with respect to a constant (integer) $k$ (which
depends on $\rho$, but for the sake of simplicity we suppress the dependence
on $\rho$ and use $k$ rather than $k_{\rho}$), and a partition of all
$(2k+1)$-patterns.666For the local rules we apply our conditions to, $k$ is
either $0$ or $1$, but using a variable parameter $k$ will hopefully allow to
extend our results more easily. The partition is denoted by
$({\mathcal{F}}_{\rho},{\overline{\cal F}}_{\rho})$, where ${\mathcal{F}}$
stands for _final_ and ${\overline{\cal F}}$ for _non-final_.

We shall say that a pair $(t,i)$ is final (respectively, non-final) _with
respect to ${\tt ENV}$ and $\rho$_ if ${\tt
ENV}_{t}(\Gamma_{k}(i))\in{\mathcal{F}}_{\rho}$ (respectively,
${\overline{\cal F}}_{\rho}$). Roughly speaking, if $(t,i)$ is final (with
respect to ${\tt ENV}$ and $\rho$), then location $i$ does not change from
time $t$ and onward (or, more generally, ${\tt ENV}_{t^{\prime}}(i)$ for
$t^{\prime}>t$ can be predicted based on ${\tt ENV}_{t}(i)$). Furthermore, if
$(t,i)$ is non-final, then $(t+1,i)$ is final if and only if $(t,i-1)$ or
$(t-1,i+1)$ is final (so that finality is “infectious”).

In our statements of the conditions, we make use of the parity function, which
we denote by $\textsf{parity}:\mathbb{N}\to\left\\{0,1\right\\}$ (so that
$\textsf{parity}(x)=1$ if $x$ is odd and $\textsf{parity}(x)=0$ if $x$ is
even).

Before each of the conditions is stated formally, we give a short, informal
description. It will also be useful to have a running example of a specific
rule $\rho$, which is the majority rule. Namely,
${\textrm{MAJ}}(\beta_{1},\beta_{2},\beta_{3})=1$ for any three bits
$\beta_{1},\beta_{2},\beta_{3}$, if and only if
$\beta_{1}+\beta_{2}+\beta_{3}\geq 2$. For the majority rule, $k=1$, and
${\mathcal{F}}_{{\textrm{MAJ}}}=\\{111,110,011,000,001,100\\}$ (so that
${\overline{\cal F}}_{{\textrm{MAJ}}}=\\{101,010\\}$).

The first condition says that if a location is final, then it remains final.

######  Condition 1.

Let ${\tt ENV}\in\mathcal{E}^{\rho}_{m,n}$ be an environment that evolves
according to $\rho$. For any time step $t\in[m-1]$ and location
$i\in{\mathbb{Z}_{n}}$, if ${\tt
ENV}_{t}(\Gamma_{k}(i))\in{\mathcal{F}}_{\rho}$, then ${\tt
ENV}_{t+1}(\Gamma_{k}(i))\in{\mathcal{F}}_{\rho}$.

Indeed, for the majority rule, if ${\tt ENV}_{t}(\Gamma_{1}(i))=111$, then
${\tt ENV}_{t+1}(\Gamma_{1}(i))=111\in{\mathcal{F}}_{{\textrm{MAJ}}}$, if
${\tt ENV}_{t}(\Gamma_{1}(i))=110$, then ${\tt
ENV}_{t+1}(\Gamma_{1}(i))\in\\{110,111\\}\subset{\mathcal{F}}_{{\textrm{MAJ}}}$,
and if ${\tt ENV}_{t}(\Gamma_{1}(i))=110$, then ${\tt
ENV}_{t+1}(\Gamma_{1}(i))\in\\{110,111\\}\subset{\mathcal{F}}_{{\textrm{MAJ}}}$
(analogous statements hold for ${\tt
ENV}_{t}(\Gamma_{1}(i))\in\\{000,001,100\\}$).

The second condition says that if a location is non-final, then it can become
final in one time step if and only if it has a final neighbor.

######  Condition 2.

Let ${\tt ENV}\in\mathcal{E}^{\rho}_{m,n}$ be an environment that evolves
according to $\rho$. For any time step $t\in[m-1]$ and location
$i\in{\mathbb{Z}_{n}}$, if ${\tt ENV}_{t}(\Gamma_{k}(i))\in{\overline{\cal
F}}_{\rho}$, then ${\tt ENV}_{t+1}(\Gamma_{k}(i))\in{\mathcal{F}}_{\rho}$ if
and only if ${\tt ENV}_{t}(\Gamma_{k}(i-1))\in{\mathcal{F}}_{\rho}$ or ${\tt
ENV}_{t}(\Gamma_{k}(i+1))\in{\mathcal{F}}_{\rho}$ (or both).

For the majority rule, consider the case that ${\tt
ENV}_{t}(\Gamma_{1}(i))=101$ (so that it belongs to ${\overline{\cal
F}}_{{\textrm{MAJ}}})$. In this case, ${\tt
ENV}_{t}(\Gamma_{1}(i-1))\in\\{110,010\\}$ and ${\tt
ENV}_{t}(\Gamma_{1}(i+1))\in\\{011,010\\}$. If ${\tt
ENV}_{t}(\Gamma_{1}(i-1))=110$ (which belongs to
${\mathcal{F}}_{{\textrm{MAJ}}}$), then ${\tt
ENV}_{t+1}(\Gamma_{1}(i))\in\\{110,111\\}\subset{\mathcal{F}}_{{\textrm{MAJ}}}$,
and the case that ${\tt ENV}_{t}(\Gamma_{1}(i+1))=011$ is analogous. On the
other hand, if both ${\tt ENV}_{t}(\Gamma_{1}(i-1))=010$ and ${\tt
ENV}_{t}(\Gamma_{1}(i+1))=010$ (so that they both belong to ${\overline{\cal
F}}_{{\textrm{MAJ}}}$), then ${\tt ENV}_{t+1}(\Gamma_{1}(i))=010$ (and it
belongs to ${\overline{\cal F}}_{{\textrm{MAJ}}}$ as well). Note that, if for
every location $i\in{\mathbb{Z}_{n}}$, it holds that ${\tt
ENV}_{0}(\Gamma_{1}(i))\in\left\\{010,101\right\\}$ (that is, every location
in the initial configuration is non-final), then no location would ever become
final throughout the evolution of the rule. In particular, in this case the
environment alternates between $(01)^{n/2}$ and $(10)^{n/2}$, where all the
locations are non-final.

The first two conditions intuitively imply that one can determine whether
certain locations are final or non-final using particular “past” locations
that are known to be final or non-final. The next two conditions capture the
idea that the actual _values_ at certain locations (and not only whether or
not they are final) can also be determined based on past locations.

In particular, the third condition captures how values at locations that are
final at a certain time step can be predicted using a function that depends on
“past” final locations from which they descend (and to which they are
closest).

######  Condition 3.

Let ${\tt ENV}\in\mathcal{E}^{\rho}_{m,n}$ be an environment that evolves
according to $\rho$. There exists a function
$f_{\rho}:\\{0,1\\}^{3}\to\\{0,1\\}$ for which the following holds. First,
$f_{\rho}$ is the XOR of its first argument and a subset of the other two
arguments. Second, let $(t,i)$ and $(t^{\prime},i^{\prime})$ be any two pairs
such that $(t,i)$ descends from $(t^{\prime},i^{\prime})$, ${\tt
ENV}_{t}(\Gamma_{k}(i)),{\tt
ENV}_{t^{\prime}}(\Gamma_{k}(i^{\prime}))\in{\mathcal{F}}_{\rho}$, and for
every $i^{\prime\prime}\neq i^{\prime}$ satisfying ${\rm
dist}(i,i^{\prime\prime})\leq{\rm dist}(i,i^{\prime})$ it holds that ${\tt
ENV}_{t^{\prime}}(\Gamma_{k}(i^{\prime\prime}))\in{\overline{\cal F}}_{\rho}$.
Then

${\tt ENV}_{t}(i)=f_{\rho}({\tt
ENV}_{t^{\prime}}(i^{\prime}),\textsf{parity}(t-t^{\prime}),\textsf{parity}({\rm
dist}(i,i^{\prime}))\;.$

For the majority rule, $f_{{\textrm{MAJ}}}$ is simply the identity function on
its first argument, namely, $f_{{\textrm{MAJ}}}(\beta,\cdot,\cdot)=\beta$.

The fourth condition captures how locations that are non-final at a certain
time step can be predicted using a function that depends on “past” non-final
locations from which they descend (conditioned on there not being any final
location among its ancestors in that past time step).

######  Condition 4.

Let ${\tt ENV}\in\mathcal{E}^{\rho}_{m,n}$ be an environment that evolves
according to $\rho$. There exists a function $h_{\rho}:{\overline{\cal
F}}_{\rho}\times\\{0,1\\}\times{\mathbb{Z}_{n}}\to{\overline{\cal F}}_{\rho}$
for which the following holds. First, $h_{\rho}$ is reversible in the sense
that for each fixed $\tau\in{\overline{\cal F}}_{\rho}$, $\beta\in\\{0,1\\}$
and $\ell\in{\mathbb{Z}_{n}}$, there exists a unique $\tau^{\prime}$ such that
$h_{\rho}(\tau^{\prime},\beta,\ell)=\tau$. Second, let $(t,i)$ and
$(t^{\prime},i^{\prime})$ be any two pairs such that $(t,i)$ descends from
$(t^{\prime},i^{\prime})$, ${\tt ENV}_{t}(\Gamma_{k}(i)),{\tt
ENV}_{t^{\prime}}(\Gamma_{k}(i^{\prime}))\in{\overline{\cal F}}_{\rho}$, and
${\tt ENV}_{t^{\prime}}(\Gamma_{k}(i^{\prime\prime}))\in{\overline{\cal
F}}_{\rho}$ for every $i^{\prime\prime}$ such that $(t,i)$ descends from
$(t^{\prime},i^{\prime\prime})$. Then

${\tt ENV}_{t}(\Gamma_{k}(i))=h_{\rho}({\tt
ENV}_{t^{\prime}}(\Gamma_{k}(i^{\prime})),\textsf{parity}(t-t^{\prime}),\overrightarrow{\rm
dist}(i^{\prime},i))\;.$

For the majority rule, $h_{{\textrm{MAJ}}}(010,\beta,x)=010$ if
$\beta\oplus\textsf{parity}(x)=0$ and $h_{{\textrm{MAJ}}}(010,\beta,x)=101$ if
$\beta\oplus\textsf{parity}(x)=0$. Similarly,
$h_{{\textrm{MAJ}}}(101,\beta,x)=101$ if $\beta\oplus\textsf{parity}(x)=0$ and
$h_{{\textrm{MAJ}}}(101,\beta,x)=010$ if $\beta\oplus\textsf{parity}(x)=1$.

The additional two conditions presented below are a bit more involved than
Conditions 1–4, and perhaps initially less intuitive. They do not play a role
in the definition of the meta algorithm, but are applied in the proof of Lemma
4.5 (and we recommend that the reader return to them in that context). In a
nutshell, they allow us to show that if our testing algorithm accepts the
environment ${\tt ENV}$ with high constant probability, then there exists an
environment ${\tt ENV}^{\prime}$ that evolves according to $\rho$ and is
relatively close to ${\tt ENV}$. In particular, they aid us in defining the
initial configuration ${\tt ENV}^{\prime}_{0}$ based on ${\tt ENV}_{t}$ for
some appropriate time step $t$.

######  Condition 5.

Let $\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$ be a configuration and let $[x,y]$
be an interval of locations such that
$\sigma(\Gamma_{k}(x))\in{\mathcal{F}}_{\rho}$ and
$\sigma(\Gamma_{k}(y))\in{\mathcal{F}}_{\rho}$. There exists a configuration
${\widetilde{\sigma}}\in{\mathbb{Z}_{n}}$, which differs from $\sigma$ only on
locations inside $[x,y]$, for which the following holds: For every $i\in[x,y]$
we have that ${\widetilde{\sigma}}(\Gamma_{k}(i))\in{\mathcal{F}}_{\rho}$, and
if $\sigma(\Gamma_{k}(i))\in{\mathcal{F}}_{\rho}$, then
${\widetilde{\sigma}}(i)=\sigma(i)$.

This condition also covers the special case in which $y=x$ and we interpret
$[x,y]$ as $x,x+1,\dots,x+n$ (with a slight abuse of notation).

######  Condition 6.

Let $\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$ be a configuration and
$z\in{\mathbb{Z}_{n}}$ such that $\sigma(\Gamma_{k}(z))\in{\overline{\cal
F}}_{\rho}$. Let $\nu\in\\{\tau_{k+1}:\tau\in{\mathcal{F}}_{\rho}\\}$ and
$\gamma,\gamma^{\prime}\in\\{0,1\\}$. There exists a configuration
${\widetilde{\sigma}}:{\mathbb{Z}_{n}}\to\\{0,1\\}$ for which the following
hold. There is a location $z^{\prime}\in[z+1,z+2k+1]$ where
${\widetilde{\sigma}}(\Gamma_{k}(z^{\prime}))\in{\mathcal{F}}_{\rho}$, and
$f_{\rho}({\widetilde{\sigma}}(z^{\prime}),\gamma,\textsf{parity}(z^{\prime}-z)\oplus\gamma^{\prime})=\nu$.
Furthermore, for every $i\in[z+1,z^{\prime}-1]$ it holds that
${\widetilde{\sigma}}(\Gamma_{k}(i))\in{\overline{\cal F}}_{\rho}$, and for
every $i\notin[z+k,z^{\prime}+k]$, ${\widetilde{\sigma}}(i)=\sigma(i)$.

A (symmetric) variant of the above should also hold if we replace
$z^{\prime}\in[z+1,z+2k+1]$ by $z^{\prime}\in[z-2k-1,z-1]$,
$i\in[z+1,z^{\prime}-1]$ by $i\in[z^{\prime}+1,z-1]$, and
$i\notin[z+k,z^{\prime}+k]$ by $i\notin[z^{\prime}-k,z-k]$.

##  4 The Meta-Algorithm

In this section, we present a meta-algorithm for testing evolution of local
rules that satisfy the sufficient conditions (specified in Section 3). Here we
give an algorithm whose complexity is $\lceil
n/m\rceil\cdot\text{poly}(1/{\epsilon})$ and, in Section 8, we explain how to
remove the dependence on $n/m$.

In order to precisely describe our meta-algorithm, we need to first define a
particular set of locations that we designate as the 1-dimensional grid and
the notion of violating time-location pairs with respect to the 1-dimensional
grid. The 1-dimensional grid is defined in Section 4.1 and the notion of
violating pairs is defined in Section 4.2. Then, in Section 4.3, we describe
our meta-algorithm.

We show that these conditions hold for all (non-trivial) threshold rules
(Section 9), as well as a couple of additional rules (Section 10).

###  4.1 The grid

In this subsection we introduce the notion of a one-dimensional “grid”, which
will be a central building block of the meta algorithm (and its analysis).
Recall that a configuration is a function
$\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$. A _partial_ configuration is a function
$\sigma^{\prime}:{\mathbb{Z}_{n}}\to\\{0,1\\}\cup\bot$, which will serve us to
denote restrictions of configurations to a subset of the locations.

Let $\Delta=\frac{{\epsilon}^{2}}{b_{0}}\cdot\min\\{n,m\\}$ where $b_{0}$ is a
sufficiently large constant. We assume for simplicity that $\Delta$ and
$n/\Delta$ are both integers. Let $G\subseteq{\mathbb{Z}_{n}}$ (the grid) be
the set of locations $\\{j\cdot(n/\Delta)\\}_{j=0}^{n/\Delta-1}$.

As we shall see in Section 4.3, our algorithm queries the tested environment
on all grid locations and their $k$-neighborhoods at a specific time step
$t_{1}$ (which will be set subsequently).

Let ${\tt ENV}_{t}[G]$ be the partial configuration that agrees with ${\tt
ENV}_{t}$ on all locations in $\\{\Gamma_{k}(g):g\in G\\}$ and is $\bot$
elsewhere.

######  Definition 4.1.

Given a time step $t>0$, we say that the partial configuration ${\tt
ENV}_{t}[G]$ induced by the $k$-neighborhoods of the grid locations at time
$t$ is feasible with respect to a rule $\rho$, if there exists an environment
${\tt ENV}^{\prime}$ that evolves according to $\rho$ and such that ${\tt
ENV}^{\prime}_{t}(i)={\tt ENV}_{t}(i)$ for every $i\in\Gamma_{k}(G)$. We say
in such a case that ${\tt ENV}^{\prime}$ is a feasible completion of ${\tt
ENV}_{t}[G]$ with respect to $\rho$.

######  Definition 4.2.

Given a pair of grid locations $g_{1},g_{2}\in G$, a time step $t$ and a
subset $\mathcal{S}\subset\\{0,1\\}^{2k+1}$, if for every grid location $g\in
G\cap[g_{1},g_{2}]$ it holds that ${\tt ENV}_{t}(\Gamma_{k}(g))\in S$, then we
say that the interval $[g_{1},g_{2}]$ is an $S$ grid interval with respect to
${\tt ENV}_{t}$. We say that $[g_{1},g_{2}]$ is a maximal $\mathcal{S}$ grid
interval with respect to ${\tt ENV}_{t}$, if both ${\tt
ENV}_{t}(g_{1}-\Delta)$ and ${\tt ENV}_{t}(g_{2}+\Delta)$ do not belong to
$\mathcal{S}$.

In particular, we shall be interested in the case that $\mathcal{S}$ is
${\mathcal{F}}_{\rho}$ or ${\overline{\cal F}}_{\rho}$. Note that a grid
interval $[g_{1},g_{2}]$ contains all the locations between $g_{1}$ and
$g_{2}$, and not just the grid locations. Also note that if ${\tt
ENV}_{t}(\Gamma_{k}(g))\in S$ for every $g\in G$, then by Definition 4.2,
there is no maximal $\mathcal{S}$ grid interval with respect to ${\tt
ENV}_{t}$ (we shall deal with such cases separately).

###  4.2 Violating Pairs

Let $\rho$ be a fixed local rule that satisfies all the conditions stated in
Section 3. Let $t_{1}=\frac{b_{1}\Delta}{\epsilon}$, where $b_{1}$ is a
sufficiently large constant and $\Delta$ is as defined in Section 4.1. Let
$t_{2}=t_{1}+\Delta$. We now define the concept of a violating pair
$(t,i)\in[m]\times{\mathbb{Z}_{n}}$ with respect to ${\tt ENV}_{t_{1}}$.
Generally speaking, these are pairs in the environment ${\tt ENV}$ whose
values are inconsistent with evolving according to the rule $\rho$ given the
values at the grid locations at time $t_{1}$. The definition of a violating
pair serves us later by allowing our algorithm to reject when it encounters
one, which, as we prove, happens with high constant probability if ${\tt ENV}$
is $\epsilon$-far from evolving according to the rule $\rho$.

Figure 4.1: An illustration for the sets $A$, $B$, $C$, and $U$. Here
$[g_{1},g_{2}]$ is a maximal ${\mathcal{F}}_{\rho}$ grid interval,
$g_{3}=g_{2}+\Delta$, where $[g_{3},g_{4}]$ is a maximal ${\overline{\cal
F}}_{\rho}$ grid interval, and $g_{5}=g_{4}+\Delta$ is an endpoint of a
maximal ${\mathcal{F}}_{\rho}$ grid-interval. The area marked by $A$
corresponds to pairs $(t,i)$ such that $t>t_{2}$ and
$i\in[g_{1}+t_{1},g_{2}-t_{1}]$. These pairs are supposed to be final. The
area marked by $B$ corresponds to pairs $(t,i)$ such that $t>t_{2}$,
$i\in[g_{2}-t_{1}+\Delta,g_{2}+(t-t_{1})]$, and ${\rm dist}(g_{2},i)<{\rm
dist}(g_{5},i)-\Delta$. These pairs are supposed to be final too. The area
marked by $C$ corresponds to pairs $(t,i)$ such that $t>t_{2}$,
$i\in[g_{3},g_{4}]$, and $(t,i)$ neither descends from $(t_{1},g_{3}+1)$ nor
from $(t_{1},g_{4}-1)$. These pairs are supposed to be non-final. Finally, the
areas marked by $U$ correspond to pairs $(t,i)$ such that $t>t_{2}$ and one of
the following holds: (1) $i\in[g_{2}-t_{1}+1,g_{2}(i)-t_{1}+\Delta]$; (2)
$i\in[g_{3},g_{4}]$ and either (a) $(t,i)$ descend from $(t_{1},g_{3}-\Delta)$
or $(t_{1},g_{4}+\Delta)$ and $|{\rm dist}(g_{3},i)-{\rm
dist}(g_{4},i)|\leq\Delta$, or (b) $(t,i)$ does not descend from either
$(t_{1},g_{3}-\Delta)$ or $(t_{1},g_{4}+\Delta)$ but it descends from either
$(t_{1},g_{3})$ or $(t_{1},g_{4})$.

We next define three disjoint sets of time-location pairs, denoted $A$, $B$
and $C$, and for each of these three sets we state conditions under which the
pair is considered to be a violating pair with respect to ${\tt
ENV}_{t_{1}}[G]$. The proof that the three sets are pairwise disjoint appears
in Section 5, and for an illustration, see Figure 4.1.

If ${\tt ENV}_{t_{1}}(\Gamma_{k}(g))\in{\mathcal{F}}_{\rho}$ for every $g\in
G$, then $A=\\{(t,i):t_{2}<t<m,\;i\in{\mathbb{Z}_{n}}\\}$. Otherwise, $A$ is
the set of pairs $(t,i)$ where $t_{2}<t<m$ and $i\in{\mathbb{Z}_{n}}$ such
that there exists a maximal ${\mathcal{F}}_{\rho}$ grid interval
$[g_{1}(i),g_{2}(i)]$ with respect to ${\tt ENV}_{t_{1}}$ for which
$i\in[g_{1}(i)+t_{1},g_{2}(i)-t_{1}]$.

######  Definition 4.3.

A pair $(t,i)\in A$ is said to be a violating pair with respect to ${\tt
ENV}_{t_{1}}[G]$, if at least one of the following requirements does not hold.
(1) ${\tt ENV}_{t_{2}}(\Gamma_{k}(i))\in{\mathcal{F}}_{\rho}$. (2) ${\tt
ENV}_{t}(\Gamma_{k}(i))\in{\mathcal{F}}_{\rho}$. (3) ${\tt
ENV}_{t}(i)=f_{\rho}({\tt ENV}_{t_{2}}(i),\textsf{parity}(t-t_{2}),0)$ where
$f_{\rho}$ is the function referred to in 3.

Let $B$ be the set of pairs $(t,i)$, where $t_{2}<t<m$ and
$i\in{\mathbb{Z}_{n}}$ for which the following holds. First, there exists a
maximal ${\mathcal{F}}_{\rho}$ grid interval $[g_{1}(i),g_{2}(i)]$ with
respect to ${\tt ENV}_{t_{1}}$ such that either
$i\in[g_{1}(i)-(t-t_{1}),g_{1}(i)+t_{1}-\Delta-1]$ or
$i\in[g_{2}(i)-t_{1}+\Delta+1,g_{2}(i)+(t-t_{1})]$. Second, for every other
maximal ${\mathcal{F}}_{\rho}$ grid interval $[g^{\prime}_{1},g^{\prime}_{2}]$
(with respect to ${\tt ENV}_{t_{1}}$), if
$i\in[g_{1}(i)-(t-t_{1}),g_{1}(i)+t_{1}-\Delta-1]$, then ${\rm
dist}(g_{1}(i),i)<{\rm dist}(g_{2}^{\prime},i)-\Delta$, and if
$i\in[g_{2}(i)-t_{1}+\Delta+1,g_{2}(i)+(t-t_{1})]$, then ${\rm
dist}(g_{2}(i),i)<{\rm dist}(g_{1}^{\prime},i)-\Delta$.

######  Definition 4.4.

A pair $(t,i)\in B$ is said to be a violating pair with respect to ${\tt
ENV}_{t_{1}}[G]$, if at least one of the following requirements does not hold.
(1) ${\tt ENV}_{t}(\Gamma_{k}(i))\in{\mathcal{F}}_{\rho}$. (2) Let
$[g_{1}(i),g_{2}(i)]$ be the maximal ${\mathcal{F}}_{\rho}$ grid interval
ensured by the definition of $B$ given $(t,i)$. Let $g(i)$ be the grid
location in
$G\cap\left([g_{1}(i),g_{1}(i)+t_{1}-\Delta]\cup[g_{2}(i),g_{2}(i)-t_{1}+\Delta]\right)$
that is closest to $i$ (if there are two such grid locations, then select the
one closer to $g_{1}(i)$). Then ${\tt ENV}_{t}(i)=f_{\rho}({\tt
ENV}_{t_{1}}(g(i)),\textsf{parity}(t-t_{1}),\textsf{parity}({\rm
dist}(i,g(i))))$, where $f_{\rho}$ is the function referred to in 3.

If ${\tt ENV}_{t_{1}}(\Gamma_{k}(g))\in{\overline{\cal F}}_{\rho}$ for every
$g\in G$, then $C=\\{(t,i):t_{2}<t<m,\;i\in{\mathbb{Z}_{n}}\\}$. Otherwise,
$C$ is the set of pairs $(t,i)$ where $t_{2}<t<m$ and $i\in{\mathbb{Z}_{n}}$
for which the following holds. First, there exists a maximal ${\overline{\cal
F}}_{\rho}$ grid interval $[g_{1}(i),g_{2}(i)]$ with respect to ${\tt
ENV}_{t_{1}}$ such that $i\in[g_{1}(i),g_{2}(i)]$. Second, the pair $(t,i)$
neither descends from the pair $(t_{1},g_{1}(i)+1)$ nor from the pair
$(t_{1},g_{2}(i)-1)$.

######  Definition 4.5.

A pair $(t,i)\in C$ is said to be a violating pair with respect to ${\tt
ENV}_{t_{1}}$, if at least one of the following requirements does not hold.
(1) ${\tt ENV}_{t}(\Gamma_{k}(i))\in{\overline{\cal F}}_{\rho}$. (2) Let
$g(i)\in G$ be a grid location satisfying ${\rm dist}(g(i),i)<\Delta$ (if
there are two such grid locations, then select the one closer to $g_{1}(i)$).
Then ${\tt ENV}_{t}(\Gamma_{k}(i))=h_{\rho}({\tt
ENV}_{t_{1}}(\Gamma_{k}(g(i))),\textsf{parity}(t-t_{1}),\overrightarrow{\rm
dist}(g(i),i))$.

Finally, we define the set $U$ of _uncertain_ pairs $(t,i)$, for which we
cannot determine, given ${\tt ENV}_{t_{1}}[G]$ and the corresponding pairs
$(t_{2},i)$, whether they are violating or not.

######  Definition 4.6.

The set $U$ consists of all pairs $(t,i)\in{\mathbb{Z}_{n}}\times[m]$ such
that $t>t_{2}$ and $(t,i)\notin A\cup B\cup C$.

In Section 5 show that the number of pairs $(t,i)$ belonging to the set $U$ is
relatively small, provided that ${\tt ENV}_{t_{1}}[G]$ is feasible.

###  4.3 The testing algorithm

Recall that Let $\Delta=\frac{{\epsilon}^{2}}{b_{0}}\cdot\min\\{n,m\\}$,
$t_{1}=\frac{b_{1}\Delta}{\epsilon}$, and $t_{2}=t_{1}+\Delta$ (where $b_{0}$
and $b_{1}$ are constants that will be set in the analysis).

Tester for evolution according to a rule $\rho$ 1. Query ${\tt ENV}_{t_{1}}$
on all locations in $\Gamma_{k}(G)$. If ${\tt ENV}_{t_{1}}[G]$ is infeasible
with respect to $\rho$, reject. 2. Select uniformly at random
$\Theta(\frac{1}{\epsilon})$ pairs $(t,i)$ where $i\in{\mathbb{Z}_{n}}$ and
$t_{2}<t<m$.
For each selected pair $(t,i)$, query ${\tt ENV}_{t}(\Gamma_{k}(i))$ and ${\tt
ENV}_{t_{2}}(\Gamma_{k}(i))$. 3. If some pair selected in Step 2 is a
violating pair with respect to $\rho$, then reject.
Otherwise, accept.

Figure 4.2: The testing algorithm

######  Theorem 4.3.

Let $\rho$ be any local rule that satisfies Conditions 1–6. The algorithm
described in Figure 4.2 is a one-sided error non-adaptive testing algorithm
for evolution according to $\rho$ whose query complexity is $O(\lceil
n/m\rceil/{\epsilon}^{2})$.

The bound on the query complexity of the algorithm follows from the fact that
the number of queries performed in Step 1 is $O(n/\Delta)=O(\lceil
n/m\rceil/{\epsilon}^{2})$ (recall that $k$ is a constant), and the number of
queries performed in Step 3 is $O(1/{\epsilon})$. The correctness of the
algorithm follows from the next two lemmas. We prove Lemma 4.4 in Section 6
and Lemma 4.5 in Section 7.

######  Lemma 4.4 (Completeness of the meta-algorithm).

Let $\rho$ be any local rule that satisfies Conditions 1–6. If the environment
${\tt ENV}$ evolves according to $\rho$, then the algorithm accepts with
probability 1.

######  Lemma 4.5 (Soundness of the meta-algorithm).

Let $\rho$ be any local rule that satisfies Conditions 1–6. If the environment
${\tt ENV}$ is $\epsilon$-far from evolving according to $\rho$, then the
algorithm rejects with probability at least $2/3$.

##  5 Observations and simple claims

In this subsection we present several observations and simple claims that will
be used in our proofs of Lemma 4.4 and Lemma 4.5.

The first two observations are directly implied by Conditions 1 and 2.

Let $\rho$ be a local rule that satisfies Conditions 1 and 2, ${\tt
ENV}\in\mathcal{E}^{\rho}_{m,n}$ an environment that evolves according to
$\rho$ and $(t,i)\in[m]\times{\mathbb{Z}_{n}}$. If $(t,i)$ has an ancestor
$(t^{\prime},i^{\prime})$ such that ${\tt
ENV}_{t^{\prime}}(\Gamma_{k}(i^{\prime}))\in{\mathcal{F}}_{\rho}$, then ${\tt
ENV}_{t}(\Gamma_{k}(i))\in{\mathcal{F}}_{\rho}$. Note that Section 5 implies
that if ${\tt ENV}_{t}(\Gamma_{k}(i))\in{\overline{\cal F}}_{\rho}$, then
${\tt ENV}_{t^{\prime}}(\Gamma_{k}(i^{\prime}))\in{\overline{\cal F}}_{\rho}$
for every ancestor $(t^{\prime},i^{\prime})$ of $(t,i)$.

Let $\rho$ be a local rule that satisfies Conditions 1 and 2, ${\tt
ENV}\in\mathcal{E}^{\rho}_{m,n}$ an environment that evolves according to
$\rho$ and $(t,i)\in[m]\times{\mathbb{Z}_{n}}$, $t\leq n/2$. If ${\tt
ENV}_{t}(\Gamma_{k}(i))\in{\mathcal{F}}_{\rho}$, then the location $i$ belongs
to an interval whose size is at least $2t$ such that ${\tt
ENV}^{\prime}_{t}(\Gamma_{k}(j))\in{\mathcal{F}}_{\rho}$ for every location
$j$ in this interval.

The observation below directly follows from Section 5 (as well as the
definition of the grid $G$ and Definitions 4.1 and 4.2). Let $\rho$ be a local
rule that satisfies Conditions 1 and 2. Suppose that ${\tt ENV}_{t}[G]$ for
$t\leq n/2$ is feasible with respect to $\rho$. Then for every $[g_{1},g_{2}]$
that is a maximal ${\mathcal{F}}_{\rho}$ grid interval with respect to ${\tt
ENV}_{t}$, the number of locations in $[g_{1},g_{2}]$ is at least $2t-\Delta$.

The next observation follows directly from Section 5 (as well as the
definition of $G$ and Definitions 4.1 and 4.2). Let $\rho$ be a local rule
that satisfies Conditions 1 and 2. Suppose that ${\tt ENV}_{t}[G]$ for $t\leq
n/2$ is feasible with respect to $\rho$ and let $g\in G$ be such that ${\tt
ENV}_{t}(\Gamma_{k}(g))\in{\mathcal{F}}_{\rho}$. If ${\tt ENV}^{\prime}$ is a
feasible completion of ${\tt ENV}_{t}[G]$ (with respect to $\rho$), then ${\tt
ENV}^{\prime}_{t^{\prime}}(\Gamma_{k}(i))\in{\mathcal{F}}_{\rho}$ for every
$t^{\prime}\geq t+\Delta$ and $i\in[g-\Delta,g+\Delta]$.

1, stated next, also deals with feasible completions.

######  Claim 1.

Let $\rho$ be a local rule that satisfies Conditions 1 and 2. Suppose that
${\tt ENV}_{t}[G]$ is feasible with respect to $\rho$ for $t\geq\Delta$ and
let $g\in G$ be such that both ${\tt ENV}_{t}(\Gamma_{k}(g))\in{\overline{\cal
F}}_{\rho}$ and ${\tt ENV}_{t}(\Gamma_{k}(g+\Delta))\in{\overline{\cal
F}}_{\rho}$. If ${\tt ENV}^{\prime}$ is a feasible completion of ${\tt
ENV}_{t}[G]$ (with respect to $\rho$), then ${\tt
ENV}^{\prime}_{t}(\Gamma_{k}(i))\in{\overline{\cal F}}_{\rho}$ for every
$i\in[g,g+\Delta]$.

######  Proof 5.1.

Assume, contrary to the claim, that there exists some $i\in[g,g+\Delta]$ such
that ${\tt ENV}^{\prime}_{t}(\Gamma_{k}(i))\in F_{\rho}$ (where ${\tt
ENV}^{\prime}$ is a feasible completion of ${\tt ENV}_{t}[G]$ (with respect to
$\rho$)). By Conditions 1 and 2, there must be some location $j$ such that
$(t,i)$ descends from $(0,j)$ and ${\tt
ENV}^{\prime}_{0}(\Gamma_{k}(j))\in{\mathcal{F}}_{\rho}$. But this would imply
(once again by 2), that ${\tt ENV}^{\prime}_{t}(\Gamma_{k}(g^{\prime}))\in
F_{\rho}$ for $g^{\prime}=g$ or $g^{\prime}=g+\Delta$, and we have reached a
contradiction.

Recall the definitions of the sets $A$, $B$ and $C$ from Section 4.2.

######  Claim 2.

The sets $A$, $B$, and $C$ are pairwise disjoint.

######  Proof 5.2.

We first show that $A\cap B=\emptyset$. Suppose by way of contradiction that
there exists a pair $(t,i)\in A\cap B$. In order for a pair $(t,i)$ to belong
to the set $A$, it must hold that $i\in[g_{1}^{A}+t_{1},g_{2}^{A}-t_{1}]$
where $[g_{1}^{A},g_{2}^{A}]$ is a maximal ${\mathcal{F}}_{\rho}$ grid
interval with respect to ${\tt ENV}_{t_{1}}$. In order for a pair $(t,i)\in A$
to also belong to the set $B$, it must hold that
$i\in[g_{1}^{B}-(t-t_{1}),g_{1}^{B}+t_{1}-\Delta-1]$ or
$i\in[g_{2}^{B}-t_{1}+\Delta+1,g_{2}^{B}+(t-t_{1})]$ where
$[g_{1}^{B},g_{2}^{B}]$ is a maximal ${\mathcal{F}}_{\rho}$ grid interval with
respect to ${\tt ENV}_{t_{1}}$.

Since $(t,i)\in A$, then, in particular, the location $i$ must belong to a
maximal ${\mathcal{F}}_{\rho}$ grid interval with respect to ${\tt
ENV}_{t_{1}}$. In the cases where $i\in[g_{1}^{B}-(t-t_{1}),g^{B}_{1}-1]$ and
$[g_{2}^{B}+1,g_{2}^{B}+(t-t_{1})]$, the location $i$ cannot belong to a
maximal ${\mathcal{F}}_{\rho}$ grid interval. The reason is that, first, by
the definition of the set $B$, for every other maximal ${\mathcal{F}}_{\rho}$
grid interval $[g^{\prime}_{1},g^{\prime}_{2}]\neq[g_{1}^{B},g_{2}^{B}]$ (with
respect to ${\tt ENV}_{t_{1}}$), if
$i\in[g_{1}(i)-(t-t_{1}),g_{1}(i)+t_{1}-\Delta-1]$, then ${\rm
dist}(g_{1}(i),i)<{\rm dist}(g_{2}^{\prime},i)-\Delta$, and if
$i\in[g_{2}(i)-t_{1}+\Delta+1,g_{2}(i)+(t-t_{1})]$, then ${\rm
dist}(g_{2}(i),i)<{\rm dist}(g_{1}^{\prime},i)-\Delta$. Hence, in the cases in
which $i\in[g_{1}^{B}-(t-t_{1}),g^{B}_{1}-1]$ or
$[g_{2}^{B}+1,g_{2}^{B}+(t-t_{1})]$, if the location $i$ were inside a maximal
${\mathcal{F}}_{\rho}$ grid interval, then that interval would be adjacent to
the interval $[g_{1}^{B},g_{2}^{B}]$. However, this is impossible, since
between each pair of maximal ${\mathcal{F}}_{\rho}$ grid intervals there is a
maximal ${\overline{\cal F}}_{\rho}$ grid interval with respect to ${\tt
ENV}_{t_{1}}$. Therefore, it must hold that either
$i\in[g_{1}^{B},g_{1}^{B}+t_{1}-\Delta-1]$ or
$i\in[g_{2}^{B}-t_{1}+\Delta+1,g_{2}^{B}]$. If
$[g_{1}^{A},g_{2}^{A}]\neq[g_{1}^{B},g_{2}^{B}]$, then it clearly cannot hold
that the location $i$ also belongs to $[g_{1}^{A}+t_{1},g_{2}^{A}-t_{1}]$
(because the maximal ${\mathcal{F}}_{\rho}$ grid intervals are disjoint with
respect to each other). Also, if
$[g_{1}^{A},g_{2}^{A}]=[g_{1}^{B},g_{2}^{B}]$, it also cannot hold that
$i\in[g_{1}^{A}+t_{1},g_{2}^{A}-t_{1}]$ because in this case all the locations
belonging the interval $[g_{1}^{B},g_{1}^{B}+t_{1}-\Delta-1]$ are to the left
of all the locations belonging to the interval
$[g_{1}^{A}+t_{1},g_{2}^{A}-t_{1}]$. Similarly, all the locations belonging
the interval $[g_{2}^{B}-t_{1}+\Delta+1,g_{2}^{B}]$ are to the right of all
the locations belonging to the interval $[g_{1}^{A}+t_{1},g_{2}^{A}-t_{1}]$.
Hence, if $(t,i)\in A$ then $(t,i)\notin B$, and therefore $A\cap
B=\emptyset$.

We now show that $B\cap C=\emptyset$. Suppose by way of contradiction that
there exists a pair $(t,i)\in B\cap C$. Since $(t,i)\in C$, it must hold that
$i\in[g_{1}^{C},g_{2}^{C}]$ where $[g_{1}^{C},g_{2}^{C}]$ is a maximal
${\overline{\cal F}}_{\rho}$ grid interval with respect to ${\tt ENV}_{t_{1}}$
and that $(t,i)$ neither descends from the pair $(t_{1},g_{1}^{C}+1)$ nor from
the pair $(t_{1},g_{2}^{C}-1)$. For $(t,i)$ to also belong to the set $B$, it
must hold that $i\in[g_{1}^{B}-(t-t_{1}),g_{1}^{B}+t_{1}-\Delta-1]$ or
$i\in[g_{2}^{B}-t_{1}+\Delta+1,g_{2}^{B}+(t-t_{1})]$ where
$[g_{1}^{B},g_{2}^{B}]$ is a maximal ${\mathcal{F}}_{\rho}$ grid interval with
respect to ${\tt ENV}_{t_{1}}$. However, since $(t,i)\in C$, and therefore, in
particular, the location $i$ must belong to a maximal ${\overline{\cal
F}}_{\rho}$ grid interval with respect to ${\tt ENV}_{t_{1}}$, the cases where
$i\in[g_{1}^{B},g_{1}^{B}+t_{1}-\Delta-1]$ and
$i\in[g_{2}^{B}-t_{1}+\Delta+1,g_{2}^{B}]$ cannot hold. Therefore, it must
hold that either $i\in[g_{1}^{B}-(t-t_{1}),g_{1}-1]$ or
$i\in[g_{2}^{B}+1,g_{2}^{B}+(t-t_{1})]$. If $[g_{1}^{C},g_{2}^{C}]$ and
$[g_{1}^{B},g_{2}^{B}]$ are not adjacent maximal grid intervals (adjacent in
the sense that they are at a distance of $\Delta$ from each other), then the
location $i$ cannot also belong to $[g_{1}^{C},g_{2}^{C}]$. Hence, we can
assume without loss of generality that $i\in[g_{2}^{B}+1,g_{2}^{B}+(t-t_{1})]$
and $g_{1}^{C}=g_{2}^{B}+\Delta$. Thus, ${\rm dist}(i,g_{1}^{C}+1)={\rm
dist}(i,g_{2}^{B}+\Delta+1)\leq t-t_{1}$. That is, the pair $(t,i)$ descends
from the pair $(t_{1},g_{1}^{C}+1)$, in contradiction to $(t,i)\in C$.
Therefore, no pair $(t,i)$ cannot belong to both $B$ and $C$.

Finally, to see that $A\cap C=\emptyset$, note that in order for a pair
$(t,i)$ to belong to the set $A$ it must belong to a maximal
${\mathcal{F}}_{\rho}$ grid interval with respect to ${\tt ENV}_{t_{1}}$, and
in order for a pair $(t,i)$ to belong to the set $C$ it must belong to a
maximal ${\overline{\cal F}}_{\rho}$ grid interval with respect to ${\tt
ENV}_{t_{1}}$. Therefore, no $(t,i)$ pair can belong to both $A$ and $C$, and
hence $A\cap C=\emptyset$.

In the last claim of this subsection, we bound the size of the set $U$ of
uncertain pairs (as defined in Definition 4.6).

######  Claim 3.

If ${\tt ENV}_{t_{1}}[G]$ is feasible (with respect to $\rho$), then
$|U|\leq\frac{5{\epsilon}}{b_{1}}mn$ (where $b_{1}$ is the constant in the
setting of $t_{1}=\frac{b_{1}\Delta}{{\epsilon}}$).

We note that 3 does not depend on the setting of $\Delta$, but only on the
definition of $t_{1}$ as a function of $\Delta$ (as well as the definition of
the grid $G$, which, too is defined based on $\Delta$, and in turn is used to
determine $U$).

######  Proof 5.3.

First note that if ${\tt ENV}_{t_{1}}(\Gamma_{k}(g))\in{\mathcal{F}}_{\rho}$
for every $g\in G$ or ${\tt ENV}_{t_{1}}(\Gamma_{k}(g))\in{\overline{\cal
F}}_{\rho}$ for every $g\in G$, then $U$ is empty. Hence, we assume from this
point on that neither is the case, so that there is at least one (non-empty)
maximal ${\mathcal{F}}_{\rho}$ grid interval and at least one (non-empty)
maximal ${\overline{\cal F}}_{\rho}$ grid interval.

By the definition of $U$ and the sets $A$, $B$, and $C$, a pair $(t,i)$
belongs to the set $U$ if $t>t_{2}$ and one of the following holds.

  1. 1.

There exists a maximal ${\mathcal{F}}_{\rho}$ grid interval
$[g_{1}(i),g_{2}(i)]$, such that either
$i\in[g_{1}(i)+t_{1}-\Delta,g_{1}(i)+t_{1}-1]$ or
$i\in[g_{2}(i)-t_{1}+1,g_{2}(i)-t_{1}+\Delta]$.

  2. 2.

There exists a maximal ${\overline{\cal F}}_{\rho}$ grid interval
$[g_{1}(i),g_{2}(i)]$ with respect to ${\tt ENV}_{t_{1}}$ where
$i\in[g_{1}(i),g_{2}(i)]$. Furthermore, if the pair $(t,i)$ descends from at
least one of the pairs $(t_{1},g_{1}(i)-\Delta)$ or $(t_{1},g_{2}(i)+\Delta)$,
then $|{\rm dist}(g_{1}(i),i)-{\rm dist}(g_{2}(i),i)|\leq\Delta$. Otherwise
(the pair $(t,i)$ does not descend from either $(t_{1},g_{1}(i)-\Delta)$ or
$(t_{1},g_{2}(i)+\Delta)$), the pair $(t,i)$ descends from either the pair
$(t_{1},g_{1}(i))$ or from the pair $(t_{1},g_{2}(i))$.

By Section 5, the length of each maximal ${\mathcal{F}}_{\rho}$ grid interval
at time $t_{1}$ is at least $t_{1}$. Therefore, the number of
${\mathcal{F}}_{\rho}$ grid intervals is at most
$\frac{n}{t_{1}}=\frac{{\epsilon}n}{b_{1}\Delta}$. This implies that the total
number of pairs $(t,i)\in U$ of the first type described above, is at most
$2\Delta\cdot\frac{{\epsilon}n}{b_{1}\Delta}\cdot
m=\frac{2{\epsilon}}{b_{1}}mn$. Since between every two maximal
${\overline{\cal F}}_{\rho}$ grid intervals there is a maximal ${\mathcal{F}}$
grid interval, the number of maximal ${\overline{\cal F}}_{\rho}$ grid
intervals is also upper bounded by $\frac{{\epsilon}n}{b_{1}\Delta}$. We shall
show that for each maximal ${\overline{\cal F}}$ grid interval
$[g_{1},g_{2}]$, the number of pairs in $U$ that descend from either
$(t_{1},g_{1})$ or $(t_{1},g_{2})$ is at most $3\Delta m$, and the current
claim follows.

Consider any fixed maximal ${\overline{\cal F}}_{\rho}$ grid interval
$[g_{1},g_{2}]$. The number of pairs $(t,i)$, where $i\in[g_{1},g_{2}]$, that
descend from at least one of the pairs $(t_{1},g_{1})$ or $(t_{1},g_{2})$, and
for which $|{\rm dist}(g_{1},i)-{\rm dist}(g_{2},i)|\leq\Delta$ is at most
$\Delta m$. This upper bound actually follows by using only the condition
$|{\rm dist}(g_{1},i)-{\rm dist}(g_{2},i)|\leq\Delta$. The number of pairs
$(t,i)$, where $i\in[g_{1},g_{2}]$, that do not descend from either
$(t_{1},g_{1}-\Delta)$ or $(t_{1},g_{2}+\Delta)$, but do descend from either
$(t_{1},g_{1})$ or $(t_{1},g_{2})$ is at most $2\Delta m$. This follows
directly from the definition of descending pairs.

##  6 Proof of Lemma 4.4:  (Completeness of the meta-algorithm).

Let $\rho$ be any local rule that satisfies Conditions 1–6 (where in this
proof we do not make use of Conditions 5 and 6, which are provided in the next
subsection), and let ${\tt ENV}\in\mathcal{E}^{\rho}_{m,n}$ be a dynamic
environment that evolves according to $\rho$. The only steps in which our
algorithm may reject are Step 1 and Step 3. The grid is feasible by
definition, and hence the algorithm does not reject in Step 1. To show that it
also does not reject in Step 3, we show that there are no violating pairs with
respect to ${\tt ENV}_{t_{1}}[G]$. Recall that each violating pair belongs to
one of the three sets $A$, $B$, or $C$ (as defined in Section 4.2).
Specifically, we next show that in each of the three cases ($(t,i)\in A$,
$(t,i)\in B$, and $(t,i)\in C$), the requirements (specified in Section 4.2)
for $(t,i)$ being a non-violating pair hold. In what follows, if we say that a
pair $(t,i)$ is final (similarly, non-final), then we mean with respect to
${\tt ENV}$, and when we refer to maximal grid intervals, it is always with
respect to ${\tt ENV}_{t_{1}}$, and violations are always with respect to
${\tt ENV}_{t_{1}}[G]$.

###### Pairs $(t,i)\in A$.

By the definition of $A$, $t>t_{2}$ and there exists a grid location $g(i)\in
G$ such that ${\rm dist}(i,g(i))\leq\Delta$ and ${\tt
ENV}_{t_{1}}(\Gamma_{k}(g(i)))\in{\mathcal{F}}_{\rho}$ (this holds both in the
case that ${\tt ENV}_{t_{1}}(\Gamma_{k}(g))\in{\mathcal{F}}_{\rho}$ for every
$g\in G$ and in the case that there exists a maximal ${\mathcal{F}}_{\rho}$
grid interval $[g_{1}(i),g_{2}(i)]$ such that
$i\in[g_{1}(i)+t_{1},g_{2}(i)-t_{1}]$.) By Section 5, both ${\tt
ENV}_{t_{2}}(\Gamma_{k}(i))\in{\mathcal{F}}_{\rho}$ and ${\tt
ENV}_{t}(\Gamma_{k}(i))\in{\mathcal{F}}_{\rho}$. Turning to the third
requirement, by 3, applied with $t^{\prime}=t_{2}$ and $i^{\prime}=i$, we get
that ${\tt ENV}_{t}(i)=f_{\rho}({\tt
ENV}_{t_{2}}(i),\textsf{parity}(t-t_{2}),0)$. Therefore, all three
requirements on pairs in $A$ hold, and hence $(t,i)$ is not a violating pair.

###### Pairs $(t,i)\in B$.

By the definition of $B$, $t>t_{2}$ and there exists a maximal
${\mathcal{F}}_{\rho}$ grid interval $[g_{1}(i),g_{2}(i)]$ with respect to
${\tt ENV}_{t_{1}}$ such that either
$i\in[g_{1}(i)-(t-t_{1}),g_{1}(i)+t_{1}-\Delta-1]$ or
$i\in[g_{2}(i)-t_{1}+\Delta+1,g_{2}(i)+(t-t_{1})]$. Furthermore, for every
other maximal ${\mathcal{F}}_{\rho}$ grid interval
$[g^{\prime}_{1},g^{\prime}_{2}]$ (with respect to ${\tt ENV}_{t_{1}}$), if
$i\in[g_{1}(i)-(t-t_{1}),g_{1}(i)+t_{1}-\Delta-1]$, then ${\rm
dist}(g_{1}(i),i)<{\rm dist}(g_{2}^{\prime},i)-\Delta$, and if
$i\in[g_{2}(i)-t_{1}+\Delta+1,g_{2}(i)+(t-t_{1})]$, then ${\rm
dist}(g_{2}(i),i)<{\rm dist}(g_{1}^{\prime},i)-\Delta$. Let $g(i)$ be the grid
location closest to $i$ in
$G\cap\left([g_{1}(i),g_{1}(i)+t_{1}-\Delta]\cup[g_{2}(i)-t_{1}+\Delta,g_{2}(i)]\right)$
(as defined in the second requirement concerning (non-)violating pairs
$(t,i)\in B$).

We claim that $(t,i)$ descends from $(0,g(i))$. To see why, first consider the
case in which
$i\in[g_{1}(i)-(t-t_{1}),g_{1}(i)]\cup[g_{2}(i),g_{2}(i)+(t-t_{1})]$. In this
case, either $g(i)=g_{1}(i)$ or $g(i)=g_{2}(i)$, which means that ${\rm
dist}(i,g(i))\leq t-t_{1}\leq t$. Second, consider the case in which
$i\in[g_{1}(i),g_{1}(i)+t_{1}-\Delta-1]\cup[g_{2}(i)-t_{1}+\Delta+1,g_{2}(i)]$.
In this case, the grid location closest to $i$ in
$G\cap\left([g_{1}(i),g_{1}(i)+t_{1}-\Delta]\cup[g_{2}(i)-t_{1}+\Delta,g_{2}(i)]\right)$
is within a distance of at most $\Delta$ from the location $i$. Hence, ${\rm
dist}(i,g(i))\leq\Delta\leq t$. Therefore, in any case, ${\rm
dist}(i,g(i))\leq t$, and thus the pair $(t,i)$ descends from the pair
$(0,g(i))$.

Assume (without loss of generality) that
$g(i)\in[g_{2}(i)-t_{1}+\Delta,g_{2}(i)]$. Since ${\tt
ENV}_{t_{1}}(\Gamma_{k}(g_{2}(i)+\Delta))\in{\overline{\cal F}}_{\rho}$ (as
$[g_{1}(i),g_{2}(i)]$ is a maximal final grid interval), we know (by Section
5) that ${\tt ENV}_{0}(\Gamma_{k}(j))\in{\overline{\cal F}}_{\rho}$ for every
$j\in[g_{2}(i)+\Delta-t_{1},g_{2}(i)+\Delta+t_{1}]$. However, since ${\tt
ENV}_{t_{1}}(\Gamma_{k}(g_{2}(i))\in{\mathcal{F}}_{\rho}$, there must be some
location $\ell\in[g_{2}(i)-t_{1},g_{2}(i)+\Delta-t_{1}-1]$ such that ${\tt
ENV}_{0}(\Gamma_{k}(\ell))\in{\mathcal{F}}_{\rho}$. Among the locations $\ell$
that satisfy these conditions, let $\ell^{*}$ be the one that minimizes ${\rm
dist}(\ell,g_{2}(i)+\Delta-t_{1})$, so that for every
$\ell^{\prime}\in[\ell^{*}+1,g_{2}(i)+\Delta-t_{1}]$ we have that ${\tt
ENV}_{0}(\Gamma_{k}(\ell^{\prime}))\in{\overline{\cal F}}_{\rho}$. Hence, for
every $i^{\prime\prime}\neq g(i)$ satisfying ${\rm
dist}(g(i),i^{\prime\prime})\leq{\rm dist}(g(i),\ell^{*})$ it holds that ${\tt
ENV}_{0}(i^{\prime\prime})\in{\overline{\cal F}}_{\rho}$. Additionally, since
$g(i)\in[g_{2}(i)-t_{1}+\Delta,g_{2}(i)]$ and
$\ell^{*}\in[g_{2}(i)-t_{1},g_{2}(i)+\Delta-t_{1}-1]$, it must hold that ${\rm
dist}(g(i),\ell^{*})\leq t_{1}$, which means that the pair $(t_{1},g(i))$
descends from the pair $(0,\ell^{*})$. Also, both ${\tt
ENV}_{t_{1}}(g(i))\in{\mathcal{F}}_{\rho}$ and ${\tt
ENV}_{0}(\ell^{*})\in{\mathcal{F}}_{\rho}$. Thus, we can apply 3 for the two
pairs $(0,\ell^{*})$ and $(t_{1},g(i))$ to get that ${\tt
ENV}_{t_{1}}(g(i))=f_{\rho}({\tt
ENV}_{0}(\ell^{*}),\textsf{parity}(t_{1}),\textsf{parity}({\rm
dist}(\ell^{*},g(i))))$.

Since the pair $(t,i)$ descends from the pair $(t_{1},g(i))$, and the pair
$(t_{1},g(i))$ descends from the pair $(0,\ell^{*})$, it holds that the pair
$(t,i)$ must also descend from the pair $(0,\ell^{*})$. Additionally, both
both ${\tt ENV}_{t}(i)\in{\mathcal{F}}_{\rho}$ and ${\tt
ENV}_{0}(\ell^{*})\in{\mathcal{F}}_{\rho}$. Also, by the second requirement on
$(t,i)$, involving other maximal ${\mathcal{F}}_{\rho}$ grid intervals
$[g^{\prime}_{1},g^{\prime}_{2}]$, for every $i^{\prime\prime}\neq i$
satisfying ${\rm dist}(i,i^{\prime\prime})\leq{\rm dist}(i,\ell^{*})$ it holds
that ${\tt ENV}_{0}(i^{\prime\prime})\in{\overline{\cal F}}_{\rho}$. Thus, we
can apply 3 for the two pairs $(0,\ell^{*})$ and $(t,i)$ to get that ${\tt
ENV}_{t}(i)=f_{\rho}({\tt
ENV}_{0}(\ell^{*}),\textsf{parity}(t),\textsf{parity}({\rm
dist}(\ell^{*},i)))$. But then, since $f_{\rho}$ is the XOR of its first
argument and a subset of the other two, and
$\textsf{parity}(t-t_{1})=\textsf{parity}(t_{1})\oplus\textsf{parity}(t)$ as
well as $\textsf{parity}({\rm dist}(g(i),i)))=\textsf{parity}({\rm
dist}(\ell^{*},g(i)))\oplus\textsf{parity}({\rm dist}(\ell^{*},i))$, we get
that ${\tt ENV}_{t}(i)=f_{\rho}({\tt
ENV}_{t_{1}}(g(i)),\textsf{parity}(t-t_{1}),\textsf{parity}({\rm
dist}(g(i),i)))$.

###### Pairs $(t,i)\in C$.

There are two cases (where in both $t>t_{2}$). The first is that ${\tt
ENV}_{t_{1}}(\Gamma_{k}(g))\in{\overline{\cal F}}_{\rho}$ for every $g\in G$
(so that $i$ may be any location in ${\mathbb{Z}_{n}}$). In the second case
there exists a maximal ${\overline{\cal F}}_{\rho}$ grid interval
$[g_{1}(i),g_{2}(i)]$ such that $i\in[g_{1}(i),g_{2}(i)]$, and $(t,i)$ does
not descend from either $(t_{1},g_{1}(i)-1)$ or $(t_{1},g_{2}(i)+1)$, which
implies that for every $j\in{\mathbb{Z}_{n}}$, if the pair $(t,i)$ descends
from $(t_{1},j)$, then $j\in[g_{1}(i),g_{2}(i)]$. In both cases, by 1, all
ancestors $(t_{1},j)$ of $(t,i)$ satisfy ${\tt
ENV}_{t_{1}}(\Gamma_{k}(j))\in{\overline{\cal F}}_{\rho}$. By Section 5 this
implies that ${\tt ENV}_{t}(\Gamma_{k}(i))\in{\overline{\cal F}}_{\rho}$, so
that the first requirement is met. As for the second requirement, since the
grid location $g(i)$ defined in the second requirement is such that
$(t_{1},g(i))$ is an ancestor of $(t,i)$ (and ${\tt
ENV}_{t_{1}}(\Gamma_{k}(g(i)))\in{\overline{\cal F}}_{\rho}$), we can apply 4
(with $t^{\prime}=t_{1}$ and $i^{\prime}=g$) to get that ${\tt
ENV}_{t}(\Gamma_{k}(i))=h_{\rho}({\tt
ENV}_{t_{1}}(\Gamma_{k}(g(i))),\textsf{parity}(t-t_{1}),\overrightarrow{\rm
dist}(g(i),i)$, as required.

We’ve shown that under the premise of the lemma, there is no pair $(t,i)\in
A\cup B\cup C$ that is a violating pair. Thus, our algorithm cannot reject at
Step 3.

##  7 Proof of Lemma 4.5:  (Soundness of the meta-algorithm).

Let ${\tt ENV}$ be any environment that is $\epsilon$-far from evolving
according to $\rho$, where $\rho$ is a local rule that satisfies Conditions
1–6. If ${\tt ENV}_{t_{1}}[G]$ is infeasible with respect to $\rho$, then the
algorithm rejects (in Step 1). Hence, we assume from now on that ${\tt
ENV}_{t_{1}}[G]$ is feasible.

We claim that the number of violating pairs with respect to ${\tt
ENV}_{t_{1}}[G]$ is at least $\frac{{\epsilon}}{b_{2}}mn$, where $b_{2}>1$ is
a constant. Lemma 4.5 follows, since the algorithm selects
$s=\Theta(1/{\epsilon})$ pairs (in Step 2), and rejects if any of them is
found to be a violating pair (in Step 3). Hence, the probability that the
algorithm rejects is at least $1-(1-{\epsilon}/b_{2})^{s}$, which is at least
$2/3$ for $s\geq 2b_{2}/{\epsilon}$.

Suppose by way of contradiction that there are less than
$\frac{{\epsilon}}{b_{2}}mn$ violating pairs. We show how, based on ${\tt
ENV}$ (to be precise, ${\tt ENV}_{t_{1}}[G]$ and ${\tt ENV}_{t_{2}}$) we can
define an environment ${\tt ENV}^{\prime}$ for which the following holds.
First, ${\tt ENV}^{\prime}$ evolves according to $\rho$. Second, ${\tt
ENV}^{\prime}$ differs from ${\tt ENV}$ on at most ${\epsilon}mn$ pairs
$(t,i)\in{\mathbb{Z}_{n}}\times[m]$. But this contradicts the premise that
${\tt ENV}$ is $\epsilon$-far from evolving according to $\rho$. Details
follow in the next subsections.

We first provide all details (in Section 7.1 and Section 7.2) under the
assumption that there exist grid locations $g\in G$ for which ${\tt
ENV}_{t_{1}}(\Gamma_{k}(g))\in{\mathcal{F}}_{\rho}$ as well as grid locations
$g^{\prime}\in G$ for which ${\tt
ENV}_{t_{1}}(\Gamma_{k}(g^{\prime}))\in{\overline{\cal F}}_{\rho}$. We discuss
(in Section 7.3) the two special cases for which either ${\tt
ENV}_{t_{1}}(\Gamma_{k}(g))\in{\mathcal{F}}_{\rho}$ for every $g\in G$ or
${\tt ENV}_{t_{1}}(\Gamma_{k}(g))\in{\overline{\cal F}}_{\rho}$ for every
$g\in G$, which we refer to as the _homogeneous_ cases.

###  7.1 The definition of ${\tt ENV}^{\prime}$

To construct the dynamic environment ${\tt ENV}^{\prime}$, we define its
initial configuration ${\tt ENV}^{\prime}_{0}$, and then apply the local rule
$\rho$ for $m-1$ steps. Hence, ${\tt ENV}^{\prime}$ evolves according to
$\rho$ by construction. The initial configuration ${\tt ENV}^{\prime}_{0}$ is
defined with respect to a configuration $\sigma$ on which we perform several
transformations to obtain ${\tt ENV}^{\prime}_{0}$. We define the
configuration $\sigma$ by specifying the value of $\sigma(i)$ for each
location $i\in{\mathbb{Z}_{n}}$ as explained next. In what follows, whenever
we refer to maximal ${\overline{\cal F}}_{\rho}$ grid intervals (similarly,
maximal ${\mathcal{F}}_{\rho}$ grid intervals), it is with respect to ${\tt
ENV}_{t_{1}}$.

We shall make use of a function $h_{\rho}^{\leftarrow}:{\overline{\cal
F}}_{\rho}\times\\{0,1\\}\times{\mathbb{Z}_{n}}$ (based on $h_{\rho}$ – see
4). Recall that by 4, for each fixed $\tau\in{\overline{\cal F}}_{\rho}$,
$\beta\in\\{0,1\\}$ and $\ell\in{\mathbb{Z}_{n}}$, there exists a unique
$\tau^{\prime}$ such that $h_{\rho}(\tau^{\prime},\beta,\ell)=\tau$.

######  Definition 7.1.

For any $\tau\in{\overline{\cal F}}_{\rho}$, $\beta\in\\{0,1\\}$ and
$\ell\in{\mathbb{Z}_{n}}$, $h_{\rho}^{\leftarrow}(\tau,\beta,\ell)$ equals the
(unique) pattern $\tau^{\prime}$ for which
$h_{\rho}(\tau^{\prime},\beta,\ell)=\tau$.

We also make the following observation, based on 3, by which $f_{\rho}$ is the
XOR of its first argument and a subset of the other two. For any
$\beta_{1},\beta_{2},\beta_{3}\in\\{0,1\\}$, if
$f_{\rho}(\beta_{1},\beta_{2},\beta_{3})=\beta_{1}^{\prime}$, then
$f_{\rho}(\beta_{1}^{\prime},\beta_{2},\beta_{3})=\beta_{1}$. Furthermore, for
any $\beta_{2}^{\prime},\beta_{3}^{\prime}\in\\{0,1\\}$,
$f_{\rho}(f_{\rho}(\beta_{1},\beta_{2},\beta_{3}),\beta^{\prime}_{2},\beta^{\prime}_{3})=f_{\rho}(\beta_{1},\beta_{2}\oplus\beta_{2}^{\prime},\beta_{3}\oplus\beta_{3}^{\prime})$,
and in particular,
$f_{\rho}(f_{\rho}(\beta_{1},\beta_{2},\beta_{3}),\beta_{2},\beta_{3})=\beta_{1}$.

For each maximal ${\overline{\cal F}}_{\rho}$ grid interval $[g_{1},g_{2}]$,
let $J(g_{1},g_{2})=[g_{1}-t_{1}-k,g_{2}+t_{1}+k]$ and let $J$ be the union
over all such sets. We also define
$J_{1}(g_{1},g_{2})=[g_{1}-t_{1},g_{2}+t_{1}]$ (for each ${\overline{\cal
F}}_{\rho}$ grid interval $[g_{1},g_{2}]$), and let $J_{1}\subset J$ be the
union over all such sets.

We first establish two simple claims.

######  Claim 4.

Let $\rho$ be any local rule that satisfies Conditions 1–4. For every two
maximal ${\overline{\cal F}}_{\rho}$ grid interval $[g_{1},g_{2}]$ and
$[g_{1}^{\prime},g_{2}^{\prime}]$, we have that $J(g_{1},g_{2})\cap
J(g^{\prime}_{1},g^{\prime}_{2})=\emptyset$.

######  Proof 7.2.

Since $[g_{1},g_{2}]$ and $[g_{1}^{\prime},g_{2}^{\prime}]$ are maximal
${\overline{\cal F}}_{\rho}$ grid intervals, we know that $g_{1}-\Delta$,
$g_{2}+\Delta$, $g_{1}^{\prime}-\Delta$ and $g_{2}^{\prime}+\Delta$ are
endpoints of maximal ${\mathcal{F}}_{\rho}$ grid intervals (with respect to
${\tt ENV}_{t_{1}}[G]$). By Section 5 these maximal ${\mathcal{F}}_{\rho}$
grid intervals are of size at least $2t_{1}$ each. As $k$ is a constant while
$\Delta=\Theta({\epsilon}^{2}\min\\{n,m\\})$, we get that
$[g_{1}-t_{1}-k,g_{2}+t_{1}+k]$ must be disjoint from
$[g^{\prime}_{1}-t_{1}-k,g^{\prime}_{2}+t_{1}+k]$.

######  Claim 5.

Let $\rho$ be any local rule that satisfies Conditions 1–4. Let ${\tt
ENV}^{\prime\prime}$ be any environment that is a feasible extension of ${\tt
ENV}_{t_{1}}[G]$ with respect to $\rho$, and let $[g_{1},g_{2}]$ be a maximal
${\overline{\cal F}}_{\rho}$ grid interval (with respect to ${\tt
ENV}_{t_{1}}[G]$). Then ${\tt
ENV}^{\prime\prime}_{0}(\Gamma_{k}(i))\in{\overline{\cal F}}_{\rho}$ for every
$i\in J_{1}(g_{1},g_{2})$. Furthermore, ${\tt
ENV}^{\prime\prime}_{0}(\Gamma_{k}(i))=h_{\rho}^{\leftarrow}({\tt
ENV}_{t_{1}}(\Gamma_{k}(g)),\textsf{parity}(t_{1}),\overrightarrow{\rm
dist}(i,g))$ for any $g\in G\cap[g_{1},g_{2}]$ and every ancestor $(0,i)$ of
$(t_{1},g)$.

######  Proof 7.3.

The first part of the claim follows from 1 and 2. Namely, assume, contrary to
the claim, that ${\tt
ENV}^{\prime\prime}_{0}(\Gamma_{k}(i))\in{\mathcal{F}}_{\rho}$ for some
$g_{1}-t_{1}\leq i\leq g_{2}+t_{2}$. But then, by 1 and 2, there would be at
least one grid location $g\in G\cap[g_{1},g_{2}]$ such that ${\tt
ENV}^{\prime\prime}_{t_{1}}(\Gamma_{k}(g))\in{\mathcal{F}}_{\rho}$. This
stands in contradiction to $[g_{1},g_{2}]$ being a maximal ${\overline{\cal
F}}_{\rho}$ grid interval with respect to ${\tt ENV}_{t_{1}}[G]$, and ${\tt
ENV}^{\prime\prime}$ being a feasible extension of ${\tt ENV}_{t_{1}}[G]$.

As for the second part of the claim, by 4 (which can be applied given the
first part of the claim), for any $i$ and $g$ as defined in the claim, ${\tt
ENV}^{\prime\prime}_{t_{1}}(\Gamma_{k}(g))=h_{\rho}({\tt
ENV}^{\prime\prime}_{0}(\Gamma_{k}(i)),\textsf{parity}(t_{1}),\overrightarrow{\rm
dist}(i,g))$. But then, by the definition of $h_{\rho}^{\leftarrow}$ and that
premise that ${\tt ENV}^{\prime\prime}$ is a feasible extension of ${\tt
ENV}_{t_{1}}[G]$, ${\tt
ENV}^{\prime\prime}_{0}(\Gamma_{k}(i))=h_{\rho}^{\leftarrow}({\tt
ENV}_{t_{1}}(\Gamma_{k}(g)),\textsf{parity}(t_{1}),\overrightarrow{\rm
dist}(i,g))$, as claimed.

Observe that 5 implies that ${\tt ENV}^{\prime\prime}_{0}$ is _uniquely_
determined by ${\tt ENV}_{t_{1}}[G]$ on all location in $J$ for every ${\tt
ENV}^{\prime\prime}$ that is a feasible extension of ${\tt ENV}_{t_{1}}[G]$
(with respect to $\rho$). Based on this observation, we start by setting the
locations of $\sigma$ that belong to $J$ as in such ${\tt
ENV}^{\prime\prime}_{0}$. In particular we have that
$\sigma(\Gamma_{k}(i))\in{\overline{\cal F}}_{\rho}$ for every $i\in J_{1}$,
and furthermore,

$\begin{split}\forall i\in J_{1},g\in G&\text{ s.t. }(t_{1},g)\text{ descends
from }(0,i)\text{ and,}\\\ &\sigma(\Gamma_{k}(i))=h_{\rho}^{\leftarrow}({\tt
ENV}_{t_{1}}(\Gamma_{k}(g)),\textsf{parity}(t_{1}),\overrightarrow{\rm
dist}(i,g))\;.\end{split}$ (7.1)

Turning to the locations not yet set in $\sigma$, for each location
$i\in{\mathbb{Z}_{n}}\setminus J$,

$\sigma(i)=f_{\rho}({\tt ENV}_{t_{2}}(i),\textsf{parity}(t_{2}),0)\;.$

Note that by Section 7.1, $f_{\rho}(\sigma(i),\textsf{parity}(t_{2}),0)={\tt
ENV}_{t_{2}}(i)$.

We next explain how we modify $\sigma$ so as to obtain ${\tt
ENV}^{\prime}_{0}$ using 5 and 6. The modifications are performed (strictly)
within the following set of intervals $\mathcal{S}$.

$\mathcal{S}=\left\\{\big{[}a=g_{1}-\Delta+t_{1},b=g_{2}+\Delta-
t_{1}\big{]}\medspace{}:\medspace{}\text{$[g_{1},g_{2}]$ is a maximal
${\mathcal{F}}_{\rho}$ grid interval }\right\\}\;.$ (7.2)

The intervals in $\mathcal{S}$ are clearly disjoint (as each is a sub-interval
of a different maximal ${\mathcal{F}}_{\rho}$ grid interval), and by Section
5, each is non-empty. Note that for each maximal ${\mathcal{F}}_{\rho}$ grid
interval $[g_{1},g_{2}]$, we have that $g_{1}-\Delta$ and $g_{2}+\Delta$ are
endpoints of maximal ${\overline{\cal F}}_{\rho}$ grid interval. Therefore,
$a,b\in J_{1}$ for each interval $[a,b]\in\mathcal{S}$, and by the setting of
$\sigma$ and 5, $\sigma(\Gamma_{k}(a)),\sigma(\Gamma_{k}(b))\in{\overline{\cal
F}}_{\rho}$.

For each $[a,b]\in\mathcal{S}$ and the corresponding $[g_{1},g_{2}]$, let
$\alpha(a,b)={\tt ENV}_{t_{1}}(g_{1})$, $\beta(a,b)={\tt ENV}_{t_{1}}(g_{2})$,
$\gamma(a,b)=\textsf{parity}(t_{1})$,
$\gamma^{\prime}(a,b)=\textsf{parity}(t_{1}-\Delta)$. We shall apply 5 and 6
to modify $\sigma$ on all $[a,b]\in\mathcal{S}$ “in parallel” as described
next, and set ${\tt ENV}^{\prime}_{0}$ to be the resulting configuration.

For each $[a,b]\in\mathcal{S}$ we first apply 6 with $z=a$, $\nu=\alpha(a,b)$,
$\gamma=\gamma(a,b)$ and $\gamma^{\prime}=\gamma^{\prime}(a,b)$. We let
$a^{\prime}=z^{\prime}$ (recall that $z^{\prime}\in[z+1,z+2k+1]$ and
${\widetilde{\sigma}}(\Gamma_{k}(z^{\prime}))\in{\mathcal{F}}_{\rho}$). Next
we apply 6 in its second (symmetric) variant with $z=b$, $\nu=\beta(a,b)$,
$\gamma=\gamma(a,b)$ and $\gamma^{\prime}=\gamma^{\prime}(a,b)$. We let
$b^{\prime}=z^{\prime}$ (recall that in this variant,
$z^{\prime}\in[z-2k-2,z-1]$, and here too
${\widetilde{\sigma}}(\Gamma_{k}(z^{\prime}))\in{\mathcal{F}}_{\rho}$).
Finally we apply 5 on the modified configuration with $x=a^{\prime}$ and
$y=b^{\prime}$.

Figure 7.1: An illustration for the setting of ${\tt ENV}_{0}$. As in Figure
4.1, $[g_{1},g_{2}]$ is a maximal ${\mathcal{F}}_{\rho}$ grid interval,
$g_{3}=g_{2}+\Delta$, where $[g_{3},g_{4}]$ is a maximal ${\overline{\cal
F}}_{\rho}$ grid interval, and $g_{5}=g_{4}+\Delta$ is an endpoint of a
maximal ${\mathcal{F}}_{\rho}$ grid-interval. The maximal ${\overline{\cal
F}}_{\rho}$ grid interval $[g_{3},g_{4}]$ is used to set the locations between
$g_{3}-t_{1}=g_{2}-t_{1}+\Delta$ and $g_{4}+t_{1}$ (more precisely, between
$g_{3}-t_{1}-k$ and $g_{4}+t_{1}+k$ based on 5. The location
$b=g_{2}-t_{1}+\Delta$ is an endpoint of an interval in $\mathcal{S}$, and the
location $b^{\prime}$ is determined by the application of 6. The values in the
$k$-neighborhood of $b^{\prime}$ are set so that the evolution of $\rho$ will
result in the ${\tt ENV}_{t_{1}}(g_{2})$ at time $t_{1}$. The pair $(t,i)$
belongs to the set $B$.

###  7.2 The distance between ${\tt ENV}$ and ${\tt ENV}^{\prime}$

In this subsection we show that based on the counter-assumption regarding the
number of violating pairs, the number of pairs
$(t,i)\in{\mathbb{Z}_{n}}\times[m]$ on which ${\tt ENV}$ and ${\tt
ENV}^{\prime}$ differ is at most ${\epsilon}mn$. To this end we show that each
$(t,i)$ such that ${\tt ENV}_{t}(i)\neq{\tt ENV}^{\prime}_{t}(i)$ belongs to
one of the following sets:

  1. 1.

The set of pairs $(t,i)$ for which $0\leq t\leq t_{2}$.

  2. 2.

The uncertainty set $U$.

  3. 3.

The set of $(t,i)$ pairs where $(t,i)$ is a violation with respect to ${\tt
ENV}_{t_{1}}[G]$.

By the setting of $t_{2}$ ($t_{1}$) and $\Delta$, the number of pairs in the
first set is at most $\frac{(b_{1}+1){\epsilon}}{b_{0}}mn$. By 3,
$|U|\leq\frac{5{\epsilon}}{b_{1}}mn$. By our counter-assumption, the number of
violating pairs is at most $\frac{{\epsilon}}{b_{2}}mn$ . Setting $b_{1}=15$,
$b_{0}=48$ and $b_{2}=3$, we get a total of at most ${\epsilon}mn$ pairs, as
claimed.

To establish the claim that each $(t,i)$ for which ${\tt ENV}_{t}(i)\neq{\tt
ENV}^{\prime}_{t}(i)$ belongs to one of the above three sets, we prove the
contrapositive. Suppose the pair $(t,i)$ is not in the uncertainty set $U$ and
that $t>t_{2}$. It follows that $(t,i)\in A\cup B\cup C$. We show that for
each of the three types of pairs ($(t,i)\in A$, $(t,i)\in B$, and $(t,i)\in
C$), if the pair $(t,i)$ is not a violating pair with respect to ${\tt
ENV}_{t_{1}}[G]$, it must hold that ${\tt ENV}_{t}(i)={\tt
ENV}^{\prime}_{t}(i)$.

###### Pairs $(t,i)\in A$.

By the definition of $A$, there exists a maximal ${\mathcal{F}}_{\rho}$ grid
interval $[g_{1}(i),g_{2}(i)]$ (with respect to ${\tt ENV}_{t_{1}}$) for which
$i\in[g_{1}(i)+t_{1},g_{2}(i)-t_{1}]$. Since $(t,i)$ is not a violating pair
with respect to ${\tt ENV}_{t_{1}}[G]$, it must hold that ${\tt
ENV}_{t_{2}}(\Gamma_{k}(i)),{\tt
ENV}_{t}(\Gamma_{k}(i))\in{\mathcal{F}}_{\rho}$ and that ${\tt
ENV}_{t}(i)=f_{\rho}({\tt ENV}_{t_{2}}(i),\textsf{parity}(t-t_{2}),0)$. Since
$i\in[g_{1}(i)+t_{1},g_{2}(i)-t_{1}]$, we know that $i\notin J$. Hence, by the
definition of the configuration $\sigma$, we have that
$\sigma(i)=f_{\rho}({\tt ENV}_{t_{2}}(i),\textsf{parity}(t_{2}),0)$ and that
$\sigma(\Gamma_{k}(i))\in{\mathcal{F}}_{\rho}$. Let
$[a(i),b(i)]=[g_{1}(i)-\Delta+t_{1},g_{2}(i)+\Delta-t_{1}]$, so that $i\in
I(a(i),b(i))$. By the definition of $E^{\prime}_{0}$, based on 5 we have that
${\tt ENV}^{\prime}_{0}(i)=\sigma(i)$ and ${\tt
ENV}^{\prime}_{0}(\Gamma_{k}(i))\in{\mathcal{F}}_{\rho}$. Since ${\tt
ENV}^{\prime}$ evolves according to $\rho$, by 3,

$\displaystyle{\tt ENV}^{\prime}_{t_{2}}(i)=f_{\rho}({\tt
ENV}^{\prime}_{0}(i),\textsf{parity}(t_{2}),0)=f_{\rho}(f_{\rho}({\tt
ENV}_{t_{2}}(i),\textsf{parity}(t_{2}),0),\textsf{parity}(t_{2}),0)={\tt
ENV}_{t_{2}}(i)$

where the last equality follows from (the second part of) Section 7.1.
Additionally, by 1, ${\tt ENV}^{\prime}_{t_{2}}(i)\in{\mathcal{F}}_{\rho}$.
Therefore, by 3,

$\displaystyle{\tt ENV}^{\prime}_{t}(i)=f_{\rho}({\tt
ENV}^{\prime}_{t_{2}}(i),\textsf{parity}(t-t_{2}),0)=f_{\rho}({\tt
ENV}_{t_{2}}(i),\textsf{parity}(t-t_{2}),0)={\tt ENV}_{t}(i)\;.$

###### Pairs $(t,i)\in B$.

By the definition of $B$, there exists a maximal ${\mathcal{F}}_{\rho}$ grid
interval $[g_{1}(i),g_{2}(i)]$ with respect to ${\tt ENV}_{t_{1}}$ such that
either $i\in[g_{1}(i)-(t-t_{1}),g_{1}(i)+t_{1}-\Delta-1]$ or
$i\in[g_{2}(i)-t_{1}+\Delta+1,g_{2}(i)+(t-t_{1})]$. Assume (without loss of
generality) that the latter holds. By the definition of $B$ we also know that
for every other maximal ${\mathcal{F}}_{\rho}$ grid interval
$[g^{\prime}_{1},g^{\prime}_{2}]$ it holds that ${\rm dist}(i,g_{2}(i))<{\rm
dist}(i,g_{1}^{\prime}),{\rm dist}(i,g_{2}^{\prime})-\Delta$. Let $g(i)$ be
the grid location closest to $i$ in $[g_{2}(i)-t_{1}+\Delta,g_{2}(i)]$. Since
$i\in[g_{2}(i)-t_{1}+\Delta+1,g_{2}(i)+(t-t_{1})]$, necessarily,
$g(i)\in[g_{2}(i)-t_{1},g_{2}(i)]$. For the sake of conciseness, in what
follows we shall use $g_{1}$, $g_{2}$, and $g$ as a shorthand for $g_{1}(i)$,
$g_{2}(i)$ and $g(i)$, respectively.

Since $[g_{1},g_{2}]$ is a maximal ${\mathcal{F}}_{\rho}$ grid interval,
$[a=g_{1}-\Delta+t_{1},b=g_{2}+\Delta-t_{1}]\in\mathcal{S}$. Hence, to obtain
${\tt ENV}^{\prime}_{0}$ from the configuration $\sigma$, we invoked 6 (the
symmetric version) with $z=b$, $\nu={\tt ENV}_{t_{1}}(g_{2})$,
$\gamma=\textsf{parity}(t_{1})$, and
$\gamma^{\prime}=\textsf{parity}(t_{1}-\Delta)=\textsf{parity}({\rm
dist}(g_{2},b))$. By 6, letting $b^{\prime}=z^{\prime}$, ${\tt
ENV}_{t_{1}}(g_{2})=f_{\rho}({\tt
ENV}^{\prime}_{0}(b^{\prime}),\textsf{parity}(t_{1}),\textsf{parity}({\rm
dist}(g_{2},b^{\prime})))$. By Section 7.1,

${\tt ENV}^{\prime}_{0}(b^{\prime})=f_{\rho}^{\leftarrow}({\tt
ENV}_{t_{1}}(g_{2}),\textsf{parity}(t_{1}),\textsf{parity}({\rm
dist}(g_{2},b^{\prime})))\;.$ (7.3)

As $b^{\prime}\in[b-2k-1,b-1]$, which by the setting of $b$ implies that
$b^{\prime}\in[g_{2}+\Delta-t_{1}-2k-1,g_{2}+\Delta-t_{1}-1]$, we have that
$(0,b^{\prime})$ is an ancestor of $(t_{1},j)$ for every
$j\in[g_{2}-t_{1},g_{2}]$. In particular this holds for the grid location $g$
(that is closest to $i$ in $G\cap[g_{2}-t_{1},g_{2}]$). Since $(t,i)$ descends
from $(t_{1},g)$, we get that $(t,i)$ also descends from $(0,b^{\prime})$.

We claim that for every $b^{\prime\prime}\neq b^{\prime}$ with ${\rm
dist}(i,b^{\prime\prime})<{\rm dist}(i,b^{\prime})$ it holds that ${\tt
ENV}^{\prime}_{0}(b^{\prime\prime})\in{\overline{\cal F}}_{\rho}$. To verify
this, let $[g_{3},g_{4}]$ be the maximal ${\overline{\cal F}}_{\rho}$ grid
interval where $g_{3}=g_{2}+\Delta$, and let $g_{5}=g_{4}+\Delta$, so that
$g_{5}$ is the endpoint of a maximal ${\mathcal{F}}_{\rho}$ grid interval. By
the definition of ${\tt ENV}^{\prime}_{0}$ (based on $\sigma$ and 6) we have
that ${\tt ENV}^{\prime}_{0}(\Gamma_{k}(j))\in{\overline{\cal F}}_{\rho}$ for
every $j\in[b^{\prime}+1,b-1]\cup
J_{1}(g_{3},g_{4})=[b^{\prime}+1,g_{4}+t_{1}]$. Since (by the second
requirements on pairs in $B$), ${\rm dist}(i,g_{2})<{\rm
dist}(i,g_{5})-\Delta$ and
$b^{\prime}\in[g_{2}-t_{1}+\Delta-2k-1,g_{2}-t_{1}+\Delta-1]$, we have that
${\tt ENV}^{\prime}_{0}(b^{\prime\prime})\in{\overline{\cal F}}_{\rho}$ for
every $b^{\prime\prime}\neq b^{\prime}$ with ${\rm
dist}(i,b^{\prime\prime})<{\rm dist}(i,b^{\prime})$. Therefore, we can apply 3
to obtain that

$\displaystyle{\tt ENV}^{\prime}_{t}(i)=f_{\rho}({\tt
ENV}_{0}(b^{\prime}),\textsf{parity}(t),\textsf{parity}({\rm
dist}(i,b^{\prime})))$ $\displaystyle=f_{\rho}(f_{\rho}({\tt
ENV}_{t_{1}}(g_{2}),\textsf{parity}(t_{1}),\textsf{parity}({\rm
dist}(g_{2},b^{\prime}))),\textsf{parity}(t),\textsf{parity}({\rm
dist}(i,b^{\prime})))$ (7.4) $\displaystyle=f_{\rho}({\tt
ENV}_{t_{1}}(g_{2}),\textsf{parity}(t-t_{1}),\textsf{parity}({\rm
dist}(i,g_{2})))$ (7.5)

where the last equality follows from Section 7.1.

Consider first the case that $g=g_{2}$. Since the pair $(t,i)$ is not a
violating pair,

${\tt ENV}_{t}(i)\;=\;f_{\rho}({\tt
ENV}_{t_{1}}(g_{2}),\textsf{parity}(t-t_{1}),\textsf{parity}({\rm
dist}(i,g_{2})))\;,$ (7.6)

and hence in this case, ${\tt ENV}_{t}(i)={\tt ENV}^{\prime}_{t}(i)$, as
desired. We next turn to the case that $g\neq g_{2}$. We claim that since
${\tt ENV}_{t_{1}}[G]$ is feasible,

${\tt ENV}_{t_{1}}(g)=f_{\rho}({\tt
ENV}^{\prime}_{0}(b^{\prime}),\textsf{parity}(t_{1}),\textsf{parity}({\rm
dist}(g,b^{\prime})))\;.$ (7.7)

Conditioned on Equality 7.7 holding, the argument is the same as for the case
that $g=g_{2}$ (replacing $g_{2}$ with $g$ in Equations (7.4)–(7.6)).

To verify Equation (7.7), we introduce the notion of a _source_ for a final
pair. Let ${\tt ENV}^{\prime\prime}$ be an environment that evolves according
to $\rho$, and $(t^{\prime},i^{\prime})$ a final pair with respect to ${\tt
ENV}^{\prime\prime}$ and $\rho$. We say that $(0,b^{\prime\prime})$ is the
_source_ of $(t^{\prime},i^{\prime})$ (at time $0$) in ${\tt
ENV}^{\prime\prime}$ if $(0,b^{\prime\prime})$ is an ancestor of
$(t^{\prime},i^{\prime})$, is final, and ${\rm
dist}(b^{\prime\prime},i^{\prime})<{\rm dist}(j,i^{\prime})$ for every other
final $(0,j)$. Consider any feasible extension $E^{\prime\prime}$ of ${\tt
ENV}_{t_{1}}[G]$. By 5 and the discussion above, the source
$(0,b^{\prime\prime})$ of $(t_{1},g_{2})$ (at time $0$ in ${\tt
ENV}^{\prime\prime}$) must satisfy
$b^{\prime\prime}\in[g_{2}-t_{1},g_{2}-t_{1}+\Delta-1]$. Furthermore,
$(0,b^{\prime\prime})$ must also be the source of $(t_{1},g^{\prime})$ for
every grid location $g^{\prime}\in[g_{2}-t_{1},g_{2}]$. Therefore, for each
such grid location, ${\tt ENV}_{t_{1}}(g^{\prime})={\tt
ENV}^{\prime\prime}_{t_{1}}(g^{\prime})=f_{\rho}({\tt
ENV}^{\prime\prime}_{0}(b^{\prime\prime}),\textsf{parity}(t_{1}),\textsf{parity}({\rm
dist}(g^{\prime},b^{\prime\prime})))$, where ${\tt
ENV}^{\prime\prime}_{0}(b^{\prime\prime})=f_{\rho}^{\leftarrow}({\tt
ENV}_{t_{1}}(g_{2}),\textsf{parity}(t_{1}),\textsf{parity}({\rm
dist}(g_{2},b^{\prime\prime})))$. If $f_{\rho}$ and $f_{\rho}^{\leftarrow}$ do
no depend on their third argument, then, by Equation (7.3), ${\tt
ENV}^{\prime}_{0}(b^{\prime})={\tt ENV}^{\prime\prime}_{0}(b^{\prime\prime})$
and if they do, then ${\tt ENV}^{\prime}_{0}(b^{\prime})={\tt
ENV}^{\prime\prime}_{0}(b^{\prime\prime})\oplus\textsf{parity}({\rm
dist}(b^{\prime},b^{\prime\prime}))$ . In either case, Equation (7.7) follows.

###### Pairs $(t,i)\in C$.

By the definition of $C$, there exists a maximal ${\overline{\cal F}}_{\rho}$
grid interval $[g_{1}(i),g_{2}(i)]$ such that $g_{1}(i)\leq i\leq g_{2}(i)$.
Additionally, the pair $(t,i)$ does not descend from either the pair
$(t_{1},g_{1}(i)-1)$ or from the pair $(t_{1},g_{2}(i)+1)$. Let $g(i)$ be the
grid location defined in Definition 4.5 (of violating pairs in $C$), so that
$g(i)\in G\cap[g_{1}(i),g_{2}(i)]$ and ${\rm dist}(i,g(i))<\Delta$.

By the definition of ${\tt ENV}^{\prime}_{0}$ (based on $\sigma$ – recall
Equation (7.1)), we have that ${\tt
ENV}^{\prime}_{0}(\Gamma_{k}(i))=h_{\rho}^{\leftarrow}({\tt
ENV}_{t_{1}}(\Gamma_{k}(g(i))),\textsf{parity}(t_{1}),\overrightarrow{\rm
dist}(i,g(i)))$. By the definition of $h_{\rho}^{\leftarrow}$ (Definition
7.1), this implies that ${\tt ENV}_{t_{1}}(\Gamma_{k}(g(i)))=h_{\rho}({\tt
ENV}^{\prime}_{0}(\Gamma_{k}(i)),\textsf{parity}(t_{1}),\overrightarrow{\rm
dist}(i,g(i)))$. Since ${\tt
ENV}^{\prime}_{0}(\Gamma_{k}(j))\in{\overline{\cal F}}_{\rho}$ for every
location $j\in J(g_{1}(i)),g_{2}(i))$, and the environment ${\tt
ENV}^{\prime}$ evolves according to $\rho$ where $\rho$ satisfies 4, we know
that ${\tt ENV}^{\prime}_{t_{1}}(\Gamma_{k}(g(i)))=h_{\rho}({\tt
ENV}^{\prime}_{0}(\Gamma_{k}(i)),\textsf{parity}(t_{1}),\overrightarrow{\rm
dist}(i,g(i)))$. Hence, ${\tt ENV}^{\prime}_{t_{1}}(\Gamma_{k}(g(i)))={\tt
ENV}_{t_{1}}(\Gamma_{k}(g(i)))$. Furthermore, using in addition the fact that
$(t,i)$ does not descend from either $(t_{1},g_{1}(i)-1)$ or
$(t_{1},g_{2}(i)+1)$, we get all ancestors of $(t_{1},j)$ of $(t,i)$ satisfy
${\tt ENV}^{\prime}_{t_{1}}(\Gamma_{k}(j))\in{\overline{\cal F}}_{\rho}$, so
that ${\tt ENV}^{\prime}_{t}(\Gamma_{k}(i))=h_{\rho}({\tt
ENV}^{\prime}_{t_{1}}(\Gamma_{k}(g(i))),\textsf{parity}(t-t_{1}),\overrightarrow{\rm
dist}(g(i),i)))$. Since $(t,i)$ is not a violating pair, ${\tt
ENV}_{t}(\Gamma_{k}(i))=h_{\rho}({\tt
ENV}_{t_{1}}(\Gamma_{k}(g(i))),\textsf{parity}(t-t_{1}),\overrightarrow{\rm
dist}(g(i),i))$, and using ${\tt ENV}^{\prime}_{t_{1}}(\Gamma_{k}(g(i)))={\tt
ENV}_{t_{1}}(\Gamma_{k}(g(i)))$ we get that ${\tt ENV}^{\prime}_{t}(i)={\tt
ENV}_{t}(i)$.

###  7.3 The homogeneous cases

Consider first the case that ${\tt
ENV}_{t_{1}}(\Gamma_{k}(g))\in{\overline{\cal F}}_{\rho}$ for every grid
location $g\in G$, which we refer to as the _fully non-final_ case. In this
case we have the following variant of 5 (whose proof is essentially the same
as the proof of 5).

######  Claim 6.

Let $\rho$ be any local rule that satisfies Conditions 1–6. Let ${\tt
ENV}^{\prime\prime}$ be any environment that is a feasible extension of ${\tt
ENV}_{t_{1}}[G]$ with respect to $\rho$, where ${\tt
ENV}_{t_{1}}(\Gamma_{k}(g))\in{\overline{\cal F}}_{\rho}$ for every $g\in G$.
Then ${\tt ENV}^{\prime\prime}_{0}(\Gamma_{k}(i))\in{\overline{\cal
F}}_{\rho}$ for every $i\in{\mathbb{Z}_{n}}$. Furthermore, ${\tt
ENV}^{\prime\prime}_{0}(\Gamma_{k}(i))=h_{\rho}^{\leftarrow}({\tt
ENV}_{t_{1}}(\Gamma_{k}(g)),\textsf{parity}(t_{1}),\overrightarrow{\rm
dist}(i,g))$ for any $g\in G$ and every ancestor $(0,i)$ of $(t_{1},g)$.

Therefore, in the fully non-final case we set ${\tt ENV}^{\prime}_{0}$ as
indicated by 6 (and let $E^{\prime}$ be the environment that evolves according
to $\rho$ from ${\tt ENV}^{\prime}_{0}$). Recall that in this case,
$C=\\{(t,i):t_{2}<t<m,\;i\in{\mathbb{Z}_{n}}\\}$ and the sets $A$ and $B$ (as
well as $U$) are empty. Therefore, the only violating pairs $(t,i)$ are those
that belong to $C$, and it suffices to show that $E^{\prime}$ and $E$ only
differ on these pairs, on top of the pairs
$(t,i)\in[t_{2}]\times{\mathbb{Z}_{n}}$. This is established as done in the
more complex heterogeneous case (for $(t,i)\in C$), and recalled next.

Consider any pair $(t,i)\in C$, and let $g(i)$ be the grid location defined in
Definition 4.5 (of violating pairs in $C$). so that ${\rm
dist}(i,g(i))<\Delta$. By the definition of ${\tt ENV}^{\prime}_{0}$ (based on
$\sigma$ – recall Equation (7.1)), we have that

${\tt ENV}^{\prime}_{0}(\Gamma_{k}(i))=h_{\rho}^{\leftarrow}({\tt
ENV}_{t_{1}}(\Gamma_{k}(g(i))),\textsf{parity}(t_{1}),\overrightarrow{\rm
dist}(i,g(i)))\;.$

By the definition of $h_{\rho}^{\leftarrow}$ (Definition 7.1), this implies
that

${\tt ENV}_{t_{1}}(\Gamma_{k}(g(i)))=h_{\rho}({\tt
ENV}^{\prime}_{0}(\Gamma_{k}(i)),\textsf{parity}(t_{1}),\overrightarrow{\rm
dist}(i,g(i)))\;.$

Since ${\tt ENV}^{\prime}_{0}(\Gamma_{k}(j))\in{\overline{\cal F}}_{\rho}$ for
every location $j\in{\mathbb{Z}_{n}}$, and the environment ${\tt
ENV}^{\prime}$ evolves according to $\rho$ where $\rho$ satisfies Condition 4,
we know that

${\tt ENV}^{\prime}_{t_{1}}(\Gamma_{k}(g(i)))=h_{\rho}({\tt
ENV}^{\prime}_{0}(\Gamma_{k}(i)),\textsf{parity}(t_{1}),\overrightarrow{\rm
dist}(i,g(i)))\;.$

Hence, ${\tt ENV}^{\prime}_{t_{1}}(\Gamma_{k}(g(i)))={\tt
ENV}_{t_{1}}(\Gamma_{k}(g(i)))$. Furthermore, we have that all ancestors of
$(t_{1},j)$ of $(t,i)$ satisfy ${\tt
ENV}^{\prime}_{t_{1}}(\Gamma_{k}(j))\in{\overline{\cal F}}_{\rho}$, so that

${\tt ENV}^{\prime}_{t}(\Gamma_{k}(i))=h_{\rho}({\tt
ENV}^{\prime}_{t_{1}}(\Gamma_{k}(g(i))),\textsf{parity}(t-t_{1}),\overrightarrow{\rm
dist}(g(i),i)))\;.$

Since $(t,i)$ is not a violating pair,

${\tt ENV}_{t}(\Gamma_{k}(i))=h_{\rho}({\tt
ENV}_{t_{1}}(\Gamma_{k}(g(i))),\textsf{parity}(t-t_{1}),\overrightarrow{\rm
dist}(g(i),i))\;,$

and using ${\tt ENV}^{\prime}_{t_{1}}(\Gamma_{k}(g(i)))={\tt
ENV}_{t_{1}}(\Gamma_{k}(g(i)))$ we get that ${\tt ENV}^{\prime}_{t}(i)={\tt
ENV}_{t}(i)$, as desired.

We now turn to the case that ${\tt
ENV}_{t_{1}}(\Gamma_{k}(g))\in{\mathcal{F}}_{\rho}$ for every $g\in G$, which
we refer to as the _fully final_ case. In this case we initialize
$\sigma(i)=f_{\rho}({\tt ENV}_{t_{2}}(i),\textsf{parity}(t_{2}),0)$ for each
$i\in{\mathbb{Z}_{n}}$, and apply 5 (on the complete interval ranging from
$a=0$ and back to $b=0$). Recall that in this fully final case,
$A=\\{(t,i):t_{2}<t<m,\;i\in{\mathbb{Z}_{n}}\\}$ and the sets $B$ and $C$ (as
well as $U$) are empty. Therefore, the only violating pairs $(t,i)$ are those
that belong to $A$, and it suffices to show that $E^{\prime}$ and $E$ only
differ on these pairs (on top of the pairs
$(t,i)\in[t_{2}]\times{\mathbb{Z}_{n}}$). This is established as done in the
more complex heterogeneous case (for $(t,i)\in A$), and recalled below.

Consider any pair $(t,i)\in A$ that is non-violating. Since $(t,i)$ is not a
violating pair with respect to ${\tt ENV}_{t_{1}}[G]$, it must hold that ${\tt
ENV}_{t_{2}}(\Gamma_{k}(i)),{\tt
ENV}_{t}(\Gamma_{k}(i))\in{\mathcal{F}}_{\rho}$ and that ${\tt
ENV}_{t}(i)=f_{\rho}({\tt ENV}_{t_{2}}(i),\textsf{parity}(t-t_{2}),0)$. By the
definition of the configuration $\sigma$, we have that
$\sigma(i)=f_{\rho}({\tt ENV}_{t_{2}}(i),\textsf{parity}(t_{2}),0)$ and that
$\sigma(\Gamma_{k}(i))\in{\mathcal{F}}_{\rho}$. By 6 and the definition of
${\tt ENV}^{\prime}_{0}$ we have that ${\tt ENV}^{\prime}_{0}(i)=\sigma(i)$
and ${\tt ENV}^{\prime}_{0}(\Gamma_{k}(i))\in{\mathcal{F}}_{\rho}$. Since
${\tt ENV}^{\prime}$ evolves according to $\rho$, by 3,

${\tt ENV}^{\prime}_{t_{2}}(i)=f_{\rho}({\tt
ENV}^{\prime}_{0}(i),\textsf{parity}(t_{2}),0)=f_{\rho}(f_{\rho}({\tt
ENV}_{t_{2}}(i),\textsf{parity}(t_{2}),0),\textsf{parity}(t_{2}),0)={\tt
ENV}_{t_{2}}(i)$

where the last equality follows from (the second part of) Section 7.1.
Additionally, by 1, ${\tt ENV}^{\prime}_{t_{2}}(i)\in{\mathcal{F}}_{\rho}$.
Therefore, by 3,

${\tt ENV}^{\prime}_{t}(i)=f_{\rho}({\tt
ENV}^{\prime}_{t_{2}}(i),\textsf{parity}(t-t_{2}),0)=f_{\rho}({\tt
ENV}_{t_{2}}(i),\textsf{parity}(t-t_{2}),0)={\tt ENV}_{t}(i)\;,$

as required.

##  8 The case of $m\ll n$

Let $\rho$ be a fixed local rule that satisfies Conditions 1–6.

In order to address the case that $m$ is much smaller than $n$ (so that the
multiplicative factor of $n/m$ in the complexity stated in Theorem 4.3 is too
large), we essentially reduce to the case that $m=\Theta({\epsilon}n)$, as
explained next. Let $n^{\prime}=b_{3}m/{\epsilon}$ (for a sufficiently large
constant $b_{3}$), and assume that $n>b_{3}m/{\epsilon}^{2}$, or else we run
the algorithm given in Section 4.3, so that we get query complexity
$O(1/{\epsilon}^{4})$. Also, assume for simplicity that $n$ is divisible by
$n^{\prime}$. We partition ${\mathbb{Z}_{n}}$ into consecutive disjoint
intervals of size $n^{\prime}$ each. The algorithm selects
$\Theta(1/{\epsilon})$ intervals, uniformly at random and for each selected
interval it runs a test to check whether the interval evolves according to
$\rho$. We next give more precise details about how such a test is performed.
At this point, we just note that the test for each selected interval performs
$O(1/{\epsilon}^{3})$ queries, so that here too we get a total of
$O(1/{\epsilon}^{4})$ queries.

Consider any such interval of size $n^{\prime}$, denoted
$I=[i_{0},j_{0}=i_{0}+n^{\prime}-1]$. Here too,
$\Delta={\epsilon}^{2}m/b_{0}$, where we assume that $n^{\prime}$ is divisible
by $\Delta$, $t_{1}=\frac{b_{1}\Delta}{\epsilon}$, and $t_{2}=t_{1}+\Delta$.
Observe that $n^{\prime}/\Delta=O(1/{\epsilon}^{3})$, and that $t_{2}\cdot
n^{\prime}=O({\epsilon}mn^{\prime})$. For $i^{\prime}_{0}=i_{0}+t_{1}+k+1$ and
$j^{\prime}_{0}=j_{0}-t_{1}-k-1$, we let
$G_{I}=\\{i^{\prime}_{0},i^{\prime}_{0}+\Delta,\dots,j^{\prime}_{0}\\}$ be the
grid associated with $I$ (we assume for simplicity that $j_{0}-i_{0}$ is
divisible by $\Delta$). The algorithm starts by querying ${\tt ENV}_{t_{1}}$
on all locations in $\Gamma_{k}(G_{I})$. If ${\tt ENV}_{t_{1}}[G_{I}]$ is
infeasible with respect to $\rho$, then the algorithm rejects. Otherwise, the
algorithm selects, uniformly at random, $\Theta(\frac{1}{\epsilon})$ pairs
$(t,i)$ where $t_{2}<t<m$ and
$i\in\\{i^{\prime}_{0}+(t-t_{1}),\dots,j^{\prime}_{0}-(t-t_{1})\\}$ (which
equals $\\{i_{0}+k+1+t,j_{0}-k-1-t\\}$). For each selected pair $(t,i)$, it
queries ${\tt ENV}_{t}(\Gamma_{k}(i))$ and ${\tt ENV}_{t_{2}}(\Gamma_{k}(i))$.
If some selected pair is a violating pair with respect to $\rho$ (as defined
in Section 4.2), then it rejects, and otherwise, it accepts. Note is that for
each interval $I=[i_{0},j_{0}]$ and for every $(t,i)$ where $t_{2}<t<m$ and
$i\in\\{i^{\prime}_{0}+(t-t_{1}),\dots,j^{\prime}_{0}-(t-t_{1})\\}$, the pair
$(t,i)$ cannot descend form a pair $(0,\ell)$ such that $\ell\notin I$.

If ${\tt ENV}$ evolves according to $\rho$, then the algorithm never rejects,
as ${\tt ENV}_{t_{1}}[G_{I}]$ is feasible for every $I$, and there are no
violating pairs with respect to ${\tt ENV}_{t_{1}}[G_{I}]$ and $\rho$, for
every $I$ (following the proof of Lemma 4.4). It remains to verify that if the
algorithm accepts ${\tt ENV}$ with probability at least $2/3$, then ${\tt
ENV}$ is ${\epsilon}$-close to some ${\tt ENV}^{\prime}$ that evolves
according to $\rho$.

We say that an interval $I=[i_{0},j_{0}]$ is _bad_ if either ${\tt
ENV}_{t_{1}}[G_{I}]$ is infeasible with respect to $\rho$ or there are more
than $({\epsilon}/b_{4})mn^{\prime}$ violating pairs $(t,i)$ (for $t_{2}<t<m$
and $i\in\\{i^{\prime}_{0}+(t-t_{1}),\dots,j^{\prime}_{0}-(t-t_{1})\\}$, where
$i^{\prime}_{0}$ and $j^{\prime}_{0}$ are as defined above and $b_{4}$ is a
sufficiently large constant). Otherwise it is _good_. Since the algorithm
accepts ${\tt ENV}$ with probability at least $2/3$, the fraction of bad
intervals is at most ${\epsilon}/b_{5}$ (for an appropriate constant $b_{5}$).
For each good interval $[i_{0},j_{0}]$ we set ${\tt ENV}^{\prime}_{0}$
restricted to (a sub-interval of)
$[i_{0}^{\prime}-(t_{1}+k),j^{\prime}_{0}-(t_{1}+k)]$ as in the proof of Lemma
4.5 (in Section 7.1). All remaining locations in ${\tt ENV}^{\prime}_{0}$
(i.e., $[i_{0},i^{\prime}_{0}-(t_{1}+k)-1]$ and
$[j^{\prime}_{0}+(t_{1}+k)+1,j_{0}]$ in each good interval $I=[i_{0},j_{0}]$,
and all of $I$ for each bad interval $I^{\prime}$), are set arbitrarily. We
let ${\tt ENV}^{\prime}$ be the environment that evolves from ${\tt
ENV}^{\prime}_{0}$ (according to $\rho$).

Following the second part of the proof of Lemma 4.5 (Section 7.2), for each
good interval $I=[i_{0},j_{0}]$, the environments ${\tt ENV}$ and ${\tt
ENV}^{\prime}$ differ on at most all locations in $[t_{2}]\times I$ (whose
number is $t_{2}\cdot n^{\prime}\leq\frac{(b_{1}+1)\Delta}{\epsilon}\cdot
n^{\prime}=\frac{b_{1}+1}{b_{0}}\cdot{\epsilon}mn^{\prime}$), on at most all
locations in $U$ restricted to $I$ (whose number is at most
$\frac{5}{b_{1}}{\epsilon}mn^{\prime}$), and on at most all violating pairs
restricted to $I$ (whose number is at most
$\frac{1}{b_{4}}{\epsilon}mn^{\prime}$). In addition, they differ on at most
all pairs $(t,i)$ where $t_{2}+1\leq t<m$ and
$i\in[i_{0},i_{0}+2m]\cup[j_{0}-2m,j_{0}]$, whose number is upper bounded by
$4m^{2}=\frac{4}{b_{3}}\cdot{\epsilon}mn^{\prime}$. They agree on all other
locations in $[m]\times I$. For each bad interval $I^{\prime}$ they may
disagree on all locations in $[m]\times I$. Summing up all disagreements
(setting e.g., $b_{1}=20$, $b_{0}=84$, $b_{4}=4$, $b_{3}=32$, and $b_{5}=8$),
we get at most ${\epsilon}mn$, as claimed.

##  9 Threshold rules

##### Complementary Rules.

Some rules are equivalent to each other in the sense that if we interchange
the roles of 0 and 1 in one rule, we get the other. Formally, two rules
$\rho,\rho^{\prime}:\\{0,1\\}^{3}\to\\{0,1\\}$ are said to be _complementary_
if for every triplet $(\beta_{1},\beta_{2},\beta_{3})\in\\{0,1\\}^{3}$, it
holds that
$\rho(\beta_{1},\beta_{2},\beta_{3})=1-\rho^{\prime}(1-\beta_{1},1-\beta_{2},1-\beta_{3})$.
Clearly, complementary rules are equivalent for testing purposes. Observe that
some rules are the complement of themselves, so the complement is an
equivalence relation that partitions the rules into pairs and singletons.

##### Threshold Rules.

Recall that a rule $\rho:\\{0,1\\}^{3}\to\\{0,1\\}$ is a _threshold_ rule if
there exist a threshold integer $0\leq b\leq 3$ and a bit
$\alpha\in\left\\{0,1\right\\}$ such that
$\rho(\beta_{1},\beta_{2},\beta_{3})=\alpha$ if and only if
$\beta_{1}+\beta_{2}+\beta_{3}\geq b$.

Since the all-$1$ and all-$0$ rules are complementary, and similarly OR and
AND as well as NOR and NAND, it suffices to consider the rules: all-$1$, OR,
NOR, Majority and Minority. The all-$1$ rule can clearly be tested with
$O(1/{\epsilon})$ queries (selected uniformly in
$[m-1]\times{\mathbb{Z}_{n}}$), as it converges in a single time step to the
all-$1$ configuration. Turning to NOR, we show that it converges in a single
time step, from which an $O(1/{\epsilon})$-query algorithm easily follows. For
the remaining, non-trivial, rules we show that they satisfy Conditions 1–6.

###  9.1 The NOR and NAND rules

We show that the NOR rule converges after at most a single time step. Since
the NAND rule is equivalent, an analogous proof holds for the NAND rule as
well.

We first claim that if at some time step $t$, every block of consecutive $0$’s
in the configuration ${\tt ENV}_{t}$ is of size at least 3, then ${\tt
ENV}_{t+2}={\tt ENV}_{t}$. Let $i\in{\mathbb{Z}_{n}}$ be a location. We show
that ${\tt ENV}_{t+2}(i)={\tt ENV}_{t}(i)$. If ${\tt ENV}_{t}(i)=1$, then
necessarily ${\tt ENV}_{t+1}(i)={\tt ENV}_{t+1}(i-1)={\tt ENV}_{t+1}(i+1)=0$,
and therefore ${\tt ENV}_{t+2}(i)={\textrm{NOR}}(0,0,0)=1={\tt ENV}_{t}(i)$.
Next consider the case that ${\tt ENV}_{t}(i)=0$. If ${\tt ENV}_{t}(i-1)={\tt
ENV}_{t}(i+1)=0$, then ${\tt ENV}_{t+1}(i)=1$, and then ${\tt ENV}_{t+2}(i)=0$
as required. Suppose this is not the case. That is, the value of either ${\tt
ENV}_{t}(i-1)$ or ${\tt ENV}_{t}(i+1)$ is $1$. Without loss of generality,
assume ${\tt ENV}_{t}(i-1)=1$. In this case, it must hold that ${\tt
ENV}_{t}(i+1)={\tt ENV}_{t}(i+2)=0$, or else the location $i$ would have been
part of a $0$-block of size less than 3. Now, ${\tt
ENV}_{t+1}(i+1)={\textrm{NOR}}(0,0,0)=1$, and therefore ${\tt
ENV}_{t+2}(i)=0$.

Now we claim that if $t>0$, there are no $0$-blocks of length less than 3 in
${\tt ENV}_{t}$. Suppose by way of contradiction that for some $t>0$, the
configuration ${\tt ENV}_{t}$ contains the pattern $101$ or $1001$. Let
$i\in{\mathbb{Z}_{n}}$ be the left-most location and $j\in{\mathbb{Z}_{n}}$ be
the right-most location in the “bad” pattern. Since ${\tt ENV}_{t}(i)={\tt
ENV}_{t}(j)=1$, it must hold that ${\tt ENV}_{t-1}(i-1)={\tt
ENV}_{t-1}(i)={\tt ENV}_{t-1}(i+1)=0$ and that ${\tt ENV}_{t-1}(j-1)={\tt
ENV}_{t-1}(j)={\tt ENV}_{t-1}(j+1)=0$. In the case of the pattern being $101$,
$i+1=j-1$. Hence, in this case, ${\tt ENV}_{t}(i+1)={\textrm{NOR}}({\tt
ENV}_{t-1}(i),{\tt ENV}_{t-1}(i+1),{\tt
ENV}_{t-1}(j))={\textrm{NOR}}(0,0,0)=1$. In the case of the pattern being
$1001$, $i+2=j-1$. Hence, in this case, ${\tt
ENV}_{t}(i+1)={\textrm{NOR}}({\tt ENV}_{t-1}(i),{\tt ENV}_{t-1}(i+1),{\tt
ENV}_{t-1}(j-1))={\textrm{NOR}}(0,0,0)=1$. That is, in both cases, ${\tt
ENV}_{t}(i+1)=1$ in contradiction to our conclusion that ${\tt
ENV}_{t}(i+1)=0$.

Now, since a $0$-block of length less than 3 can only appear in the initial
configuration, and cannot arise in any other way, and, as we’ve shown, once
there are no 0-blocks of length less than 3, the environment alternates
between a pair of configurations (that is, it has converged), any environment
that evolves according to the NOR rule converges after at most a single time
step, and hence is trivially $\text{poly}(1/{\epsilon})$-testable.

###  9.2 The OR and AND rules

We prove that all conditions hold for the rule
${\textrm{OR}}(\beta_{1},\beta_{2},\beta_{3})=\beta_{1}\vee\beta_{2}\vee\beta_{3}$.
Since the AND rule is equivalent to the OR rule, all the conditions must hold
for the AND rule as well.

For OR, $k=0$, ${\mathcal{F}}_{{\textrm{OR}}}=\\{1\\}$ (and ${\overline{\cal
F}}_{{\textrm{OR}}}=\\{0\\}$). This rule ultimately converges to the all-$1$
configuration, unless the starting configuration is the all-$0$ configuration
(in which case it remains in this configuration indefinitely). Since $k=0$,
rather than writing ${\tt ENV}_{t}(\Gamma_{0}(i))$, we simply write ${\tt
ENV}_{t}(i)$. Turning to the conditions (where the numbering of the items
below correspond to the numbering of the conditions).

  1. 1.

If ${\tt ENV}_{t}(i)\in{\mathcal{F}}_{{\textrm{OR}}}$, then ${\tt
ENV}_{t}(i)=1$, so that ${\tt ENV}_{t+1}(i)=1$ as well (for any setting of
${\tt ENV}_{t}(i-1)$ and ${\tt ENV}_{t-1}(i+1)$).

  2. 2.

If ${\tt ENV}_{t}(i)\in{\overline{\cal F}}_{{\textrm{OR}}}$, then ${\tt
ENV}_{t}(i)=0$. If either ${\tt ENV}_{t}(i-1)=1$ or ${\tt ENV}_{t}(i+1)=1$ (or
both), then ${\tt ENV}_{t+1}(i)=1\in{\mathcal{F}}_{{\textrm{OR}}}$, and
otherwise ${\tt ENV}_{t+1}(i)=0\in{\overline{\cal F}}_{{\textrm{OR}}}$.

  3. 3.

The function $f_{{\textrm{OR}}}$ simply equals its first argument (which is
$1$ whenever the function is applied).

  4. 4.

The function $h_{{\textrm{OR}}}$ simply equals its first argument (which is
necessarily $0$).

  5. 5.

Let $\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$ be a configuration and let $[x,y]$
be an interval of locations such that
$\sigma(x)\in{\mathcal{F}}_{\textrm{OR}}$ and
$\sigma(y)\in{\mathcal{F}}_{\textrm{OR}}$. That is, $\sigma(x)=\sigma(y)=1$.
We simply set ${\widetilde{\sigma}}(i)=1$ for every $i\in[x,y]$ and
${\widetilde{\sigma}}(i)=\sigma(i)$ otherwise. It clearly holds that for every
$i\in[x,y]$ we have that
${\widetilde{\sigma}}(i)=1\in{\mathcal{F}}_{\textrm{OR}}$, and if $i\in[x,y]$
and $\sigma(i)\in{\mathcal{F}}_{\textrm{OR}}$, then
${\widetilde{\sigma}}(i)=1=\sigma(i)$, and so the requirements of 5 hold.

  6. 6.

By the premise of 6 (regarding $z$), we have that $\sigma(z)=0$. We set
$z^{\prime}=z+1$ (in the symmetric version, $z^{\prime}=z-1$) and
${\widetilde{\sigma}}(z^{\prime})=1$.

###  9.3 The Majority rule

Here we repeat what was stated in Section 3 regarding the majority rule,
denoted MAJ, and add missing explanations when needed.

For this rule, $k=1$, and
${\mathcal{F}}_{{\textrm{MAJ}}}=\\{111,110,011,000,001,100\\}$ (so that
${\overline{\cal F}}_{{\textrm{MAJ}}}=\\{101,010\\}$). This rule ultimately
converges to configurations that constitute of intervals of at least two
consecutive $1$s and intervals of at least two consecutive $0$s, unless the
starting configuration is $(01)^{n/2}$ (in which case it alternates between
this configuration and the complementary one $(10)^{n/2}$).

We now verify that the conditions hold.

  1. 1.

If ${\tt ENV}_{t}(\Gamma_{1}(i))=111$, then ${\tt
ENV}_{t+1}(\Gamma_{1}(i))=111\in{\mathcal{F}}_{{\textrm{MAJ}}}$, if ${\tt
ENV}_{t}(\Gamma_{1}(i))=110$, then ${\tt
ENV}_{t+1}(\Gamma_{1}(i))\in\\{110,111\\}\subset{\mathcal{F}}_{{\textrm{MAJ}}}$,
and if ${\tt ENV}_{t}(\Gamma_{1}(i))=110$, then ${\tt
ENV}_{t+1}(\Gamma_{1}(i))\in\\{110,111\\}\subset{\mathcal{F}}_{{\textrm{MAJ}}}$
(analogous statements hold for ${\tt
ENV}_{t}(\Gamma_{1}(i))\in\\{000,001,100\\}$).

  2. 2.

Consider first the case that ${\tt ENV}_{t}(\Gamma_{1}(i))=101$ (so that it
belongs to ${\overline{\cal F}}_{{\textrm{MAJ}}})$. In this case, ${\tt
ENV}_{t}(\Gamma_{1}(i-1))\in\\{110,010\\}$ and ${\tt
ENV}_{t}(\Gamma_{1}(i+1))\in\\{011,010\\}$. If ${\tt
ENV}_{t}(\Gamma_{1}(i-1))=110$ (which belongs to
${\mathcal{F}}_{{\textrm{MAJ}}}$), then ${\tt ENV}_{t}(i-1)=1$ and ${\tt
ENV}_{t}(i)=1$, so that ${\tt
ENV}_{t+1}(\Gamma_{1}(i))\in\\{110,111\\}\subset{\mathcal{F}}_{{\textrm{MAJ}}}$
(and the case that ${\tt ENV}_{t}(\Gamma_{1}(i+1))=011$ is analogous). On the
other hand, if both ${\tt ENV}_{t}(\Gamma_{1}(i-1))=010$ and ${\tt
ENV}_{t}(\Gamma_{1}(i+1))=010$ (so that they both belong to ${\overline{\cal
F}}_{{\textrm{MAJ}}}$), then ${\tt ENV}_{t+1}(\Gamma_{1}(i))=010$ (and it
belongs to ${\overline{\cal F}}_{{\textrm{MAJ}}}$ as well).

  3. 3.

For any $\beta\in\\{0,1\\}$, we have that
$f_{{\textrm{MAJ}}}(\beta,\cdot,\cdot)=\beta$. To verify this, observe that
under the premise of the condition, one of the following holds. (1) ${\tt
ENV}_{t^{\prime}}(\Gamma_{1}(i^{\prime}))=\beta\beta\overline{\beta}$, and for
every ancestor $(t^{\prime},i^{\prime\prime})\neq(t^{\prime},i^{\prime})$ of
$(t,i)$ for which ${\rm dist}(i,i^{\prime\prime})\leq{\rm dist}(i,i^{\prime})$
it holds that ${\tt
ENV}_{t^{\prime}}(i^{\prime\prime})=\overline{\textsf{parity}(i^{\prime\prime}-i)}$.
(2) ${\tt
ENV}_{t^{\prime}}(\Gamma_{1}(i^{\prime}))=\overline{\beta}\beta\beta$ and for
every ancestor $(t^{\prime},i^{\prime\prime})$ of $(t,i)$ such ${\rm
dist}(i,i^{\prime\prime})\leq{\rm dist}(i,i^{\prime})$ it holds that ${\tt
ENV}_{t^{\prime}}(i^{\prime\prime})=\overline{\textsf{parity}(i^{\prime\prime}-i)}$.
To illustrate the first case, suppose that $t-t^{\prime}=5$, then ${\tt
ENV}_{t^{\prime}}$ between locations $i-5$ and $i+5$ may be of the form
$01110101010$ (so that at time $t^{\prime}+1$ locations $i-4$ to $i+4$ are
$111101010$, and time $t^{\prime}+2$ locations $i-3$ to $i+3$ are $1111010$,
so that $(t^{\prime}+2,i)$ has become final with respect to ${\tt
ENV}^{\prime}$ and $\rho$, and ${\tt ENV}_{t^{\prime\prime}}(i)=1$ for every
$t^{\prime\prime}\geq t^{\prime}+2$.

  4. 4.

The function $h_{{\textrm{MAJ}}}$ is defined as follows:
$h_{{\textrm{MAJ}}}(010,\beta,x)=010$ if $\beta\oplus\textsf{parity}(x)=0$ and
$h_{{\textrm{MAJ}}}(010,\beta,x)=101$ if $\beta\oplus\textsf{parity}(x)=1$.
Similarly, $h_{{\textrm{MAJ}}}(101,\beta,x)=101$ if
$\beta\oplus\textsf{parity}(x)=0$ and $h_{{\textrm{MAJ}}}(101,\beta,x)=010$ if
$\beta\oplus\textsf{parity}(x)=1$.

  5. 5.

Let $\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$ be a configuration and let $[x,y]$
be an interval of locations such that
$\sigma(\Gamma_{1}(x))\in{\mathcal{F}}_{\textrm{MAJ}}$ and
$\sigma(\Gamma_{1}(y))\in{\mathcal{F}}_{\textrm{MAJ}}$. We define the
configuration ${\widetilde{\sigma}}$ as follows. Let $i\in[(]n)$. If
$i\notin[x,y]$, we set ${\widetilde{\sigma}}(i)=\sigma(i)$. Otherwise, let
$j_{i}\in[x,y]$ be the location that minimizes ${\rm dist}(i,j)$ among the
locations for which $\sigma(\Gamma_{1}(j))\in{\mathcal{F}}_{\textrm{MAJ}}$,
and set ${\widetilde{\sigma}}(i)=\sigma(j_{i})$. In particular, note that if
$\sigma(\Gamma_{1}(i))\in{\mathcal{F}}_{\textrm{MAJ}}$, then
${\widetilde{\sigma}}(i)=\sigma(i)$. We claim that for every $i\in[x,y]$ we
have that
${\widetilde{\sigma}}(\Gamma_{1}(i))\in{\mathcal{F}}_{\textrm{MAJ}}$, and that
if $\sigma(\Gamma_{1}(i))\in{\mathcal{F}}_{\textrm{MAJ}}$, then
${\widetilde{\sigma}}(i)=\sigma(i)$. Let $i\in[x,y]$. If
$\sigma(\Gamma_{1}(i))\in{\mathcal{F}}_{\textrm{MAJ}}$, then $j_{i}=i$, and
hence either $\sigma(\Gamma_{1}(i-1))\in{\mathcal{F}}_{\textrm{MAJ}}$ or
$\sigma(\Gamma_{1}(i+1))\in{\mathcal{F}}_{\textrm{MAJ}}$, which implies that
either ${\widetilde{\sigma}}(i)={\widetilde{\sigma}}(i-1)$ or
${\widetilde{\sigma}}(i)={\widetilde{\sigma}}(i+1)$, and in both cases, it
holds that
${\widetilde{\sigma}}(\Gamma_{1}(i))\in{\mathcal{F}}_{\textrm{MAJ}}$ and
${\widetilde{\sigma}}(i)=\sigma(i)$. If
$\sigma(\Gamma_{1}(i))\in{\overline{\cal F}}_{\textrm{MAJ}}$, then, assume
without loss of generality that $j^{*}\in[i+1,y]$ (the case in which
$j^{*}\in[x,i-1]$ is similar). In this case, $j_{i}=j_{i+1}$, and hence
${\widetilde{\sigma}}(i)={\widetilde{\sigma}}(i+1)$, which implies that
${\widetilde{\sigma}}(\Gamma_{1}(i))\in{\mathcal{F}}_{\textrm{MAJ}}$.

  6. 6.

Assume first that $\sigma(\Gamma_{1}(z))=101$. If $\nu=1$, then we set
$z^{\prime}=z+1$ and ${\widetilde{\sigma}}(z+2)=1$, and if $\nu=0$, then we
set $z^{\prime}=z+2$, ${\widetilde{\sigma}}(z+2)={\widetilde{\sigma}}(z+3)=0$.
In the first case,
${\widetilde{\sigma}}(\Gamma_{1}(z^{\prime}))=011\in{\mathcal{F}}_{{\textrm{MAJ}}}$
and in the second
${\widetilde{\sigma}}(\Gamma_{1}(z^{\prime}))=100\in{\mathcal{F}}_{{\textrm{MAJ}}}$
and ${\widetilde{\sigma}}(\Gamma_{1}(z+1))=010\in{\overline{\cal
F}}_{{\textrm{MAJ}}}$. In both cases,
$f_{\rho}({\widetilde{\sigma}}(z^{\prime}),\gamma,\textsf{parity}(z^{\prime}-z)\oplus\gamma^{\prime})={\widetilde{\sigma}}(z^{\prime})=\nu$
for any $\gamma$ and $\gamma^{\prime}$. If $\sigma(\Gamma_{1}(z))=010$, then
for $\nu=0$ we set $z^{\prime}=z+1$ and ${\widetilde{\sigma}}(z+2)=0$, and for
$\nu=1$, we set $z^{\prime}=z+2$,
${\widetilde{\sigma}}(z+2)={\widetilde{\sigma}}(z+3)=1$. The symmetric variant
of this condition is established similarly.

###  9.4 The Minority rule

For the minority rule, denoted MIN, like the majority rule, $k=1$, and
${\mathcal{F}}_{{\textrm{MIN}}}=\\{111,110,011,000,001,100\\}$ (so that
${\overline{\cal F}}_{{\textrm{MIN}}}=\\{101,010\\}$). Ultimate Convergence is
also similar to the majority rule, except that in each time step, blocks of
$1$s “flip” to become blocks of $0$s and vice versa, and if the initial
configuration is $(01)^{n/2}$, then it does not change.

We now turn to the conditions.

  1. 1.

If ${\tt ENV}_{t}(\Gamma_{1}(i))=111$, then ${\tt
ENV}_{t+1}(\Gamma_{1}(i))=000\in{\mathcal{F}}_{{\textrm{MIN}}}$, if ${\tt
ENV}_{t}(\Gamma_{1}(i))=110$, then ${\tt
ENV}_{t+1}(\Gamma_{1}(i))\in\\{001,000\\}\subset{\mathcal{F}}_{{\textrm{MIN}}}$,
and if ${\tt ENV}_{t}(\Gamma_{1}(i))=011$, then ${\tt
ENV}_{t+1}(\Gamma_{1}(i))\in\\{100,000\\}\subset{\mathcal{F}}_{{\textrm{MIN}}}$
(analogous statements hold for ${\tt
ENV}_{t}(\Gamma_{1}(i))\in\\{000,001,100\\}$).

  2. 2.

Consider first the case that ${\tt ENV}_{t}(\Gamma_{1}(i))=101$ (so that it
belongs to ${\overline{\cal F}}_{{\textrm{MIN}}})$. In this case, ${\tt
ENV}_{t}(\Gamma_{1}(i-1))\in\\{110,010\\}$ and ${\tt
ENV}_{t}(\Gamma_{1}(i+1))\in\\{011,010\\}$. If ${\tt
ENV}_{t}(\Gamma_{1}(i-1))=110$ (which belongs to
${\mathcal{F}}_{{\textrm{MIN}}}$), then ${\tt ENV}_{t}(i-1)=0$ and ${\tt
ENV}_{t}(i)=0$, so that ${\tt
ENV}_{t+1}(\Gamma_{1}(i))\in\\{001,000\\}\subset{\mathcal{F}}_{{\textrm{MIN}}}$
(and the case that ${\tt ENV}_{t}(\Gamma_{1}(i+1))=011$ is analogous). On the
other hand, if both ${\tt ENV}_{t}(\Gamma_{1}(i-1))=010$ and ${\tt
ENV}_{t}(\Gamma_{1}(i+1))=010$ (so that they both belong to ${\overline{\cal
F}}_{{\textrm{MIN}}}$), then ${\tt ENV}_{t+1}(\Gamma_{1}(i))=101$ (which is
the same as ${\tt ENV}_{t}(\Gamma_{1}(i))$, and it belongs to ${\overline{\cal
F}}_{{\textrm{MIN}}}$ as well).

  3. 3.

For any $\beta\in\\{0,1\\}$, we have that
$f_{{\textrm{MIN}}}(\beta_{1},\beta_{2},\cdot)=\beta_{1}\oplus\beta_{2}$. This
can be verified similarly to what was shown for MAJ.

  4. 4.

The function $h_{{\textrm{MIN}}}$ is defined as follows:
$h_{{\textrm{MIN}}}(010,\beta,x)=101$ if $\beta\oplus\textsf{parity}(x)=0$ and
$h_{{\textrm{MIN}}}(010,\beta,x)=010$ if $\beta\oplus\textsf{parity}(x)=1$.
Similarly, $h_{{\textrm{MIN}}}(101,\beta,x)=010$ if
$\beta\oplus\textsf{parity}(x)=0$ and $h_{{\textrm{MIN}}}(101,\beta,x)=101$ if
$\beta\oplus\textsf{parity}(x)=1$.

  5. 5.

This item is the same as the corresponding one for MAJ.

  6. 6.

This item is very similar to the corresponding one for MAJ. The only
difference is that there is a dependence on the parameter $\gamma$.
Specifically, if $\gamma=0$, then the setting is exactly as for MAJ. Suppose
$\gamma=1$. We assume first that $\sigma(\Gamma_{1}(z))=101$. If $\nu=0$, then
we set $z^{\prime}=z+1$ and ${\widetilde{\sigma}}(z+2)=1$, and if $\nu=1$,
then we set $z^{\prime}=z+2$,
${\widetilde{\sigma}}(z+2)={\widetilde{\sigma}}(z+3)=0$. In the first case,
${\widetilde{\sigma}}(\Gamma_{1}(z^{\prime}))=011\in{\mathcal{F}}_{{\textrm{MIN}}}$
and in the second
${\widetilde{\sigma}}(\Gamma_{1}(z^{\prime}))=100\in{\mathcal{F}}_{{\textrm{MIN}}}$
and ${\widetilde{\sigma}}(\Gamma_{1}(z+1))=010\in{\overline{\cal
F}}_{{\textrm{MIN}}}$. In both cases,
$f_{\rho}({\widetilde{\sigma}}(z^{\prime}),\gamma,\textsf{parity}(z^{\prime}-z)\oplus\gamma^{\prime})={\widetilde{\sigma}}(z^{\prime})\oplus\gamma=1-{\widetilde{\sigma}}(z^{\prime})=\nu$
for any $\gamma^{\prime}$. If $\sigma(\Gamma_{1}(z))=010$, then for $\nu=1$ we
set $z^{\prime}=z+1$ and ${\widetilde{\sigma}}(z+2)=0$, and for $\nu=0$, we
set $z^{\prime}=z+2$, ${\widetilde{\sigma}}(z+2)={\widetilde{\sigma}}(z+3)=1$.

##  10 Other rules

###  10.1 Flip if homogeneous

This rule, denoted FIH, is defined as follows:
${\textrm{FIH}}(\beta_{1},\beta_{2},\beta_{3})=\beta_{2}$ unless
$\beta_{1}=\beta_{2}=\beta_{3}$, in which case
${\textrm{FIH}}(\beta_{1},\beta_{2},\beta_{3})=\overline{\beta}_{2}$. This
rule ultimately converges to configurations with blocks of size one or two
(unless the initial configuration is the all-$0$ configuration or the all-$1$
configuration, in which case it alternates between the two). Here we have
${\overline{\cal F}}_{{\textrm{FIH}}}=\\{000,111\\}$ (so that
${\mathcal{F}}_{{\textrm{FIH}}}=\\{01?,?10,10?,?01\\}$.

  1. 1.

If ${\tt ENV}_{t}(\Gamma_{1}(i))\in{\overline{\cal F}}_{{\textrm{FIH}}}$ then
either ${\tt ENV}_{t}(i)\neq{\tt ENV}_{t}(i-1)$ or ${\tt ENV}_{t}(i)\neq{\tt
ENV}_{t}(i+1)$ (possibly both), so that in the first case ${\tt
ENV}_{t+1}(i-1)={\tt ENV}_{t}(i-1)$ and in the second case, ${\tt
ENV}_{t+1}(i)={\tt ENV}_{t}(i)$. In both cases ${\tt ENV}_{t+1}(i+1)={\tt
ENV}_{t}(i+1)$, so that ${\tt
ENV}_{t+1}(\Gamma_{1}(i))\in{\mathcal{F}}_{{\textrm{FIH}}}$ as required.

  2. 2.

If ${\tt ENV}_{t}(\Gamma_{1}(i))\in{\overline{\cal F}}_{{\textrm{FIH}}}$, then
${\tt ENV}_{t}(\Gamma_{1}(i))\in\\{000,111\\}$. If both ${\tt
ENV}_{t}(\Gamma_{1}(i-1))\in{\overline{\cal F}}_{{\textrm{FIH}}}$ and ${\tt
ENV}_{t}(\Gamma_{1}(i-1))\in{\overline{\cal F}}_{{\textrm{FIH}}}$, then ${\tt
ENV}_{t}(\Gamma_{2}(i))\in\\{00000,11111\\}$, so that ${\tt
ENV}_{t+1}(\Gamma_{1}(i))\in\\{111,000\\}={\overline{\cal
F}}_{{\textrm{FIH}}}$. On the other hand, if ${\tt
ENV}_{t}(\Gamma_{1}(i-1))\in{\mathcal{F}}_{{\textrm{FIH}}}$ or ${\tt
ENV}_{t}(\Gamma_{1}(i+1))\in{\mathcal{F}}_{{\textrm{FIH}}}$, then ${\tt
ENV}_{t}(\Gamma_{2}(i))\in\\{1000?,?0001,0111?,?1110\\}$ so that ${\tt
ENV}_{t+1}\in\\{01?,?10,10?,?10\\}={\mathcal{F}}_{{\textrm{FIH}}}$.

  3. 3.

The function $f_{\rho}$ is defined as follows:
$f_{\rho}(\beta_{1},\beta_{2},\beta_{3})=\beta_{1}\oplus\beta_{3}$. To verify
this consider any $(t,i)$ and $(t^{\prime},i^{\prime})$ that satisfy the
requirements in 3. Assume that ${\rm dist}(i^{\prime},i)=\overrightarrow{\rm
dist}(i^{\prime},i)$ (the case that ${\rm
dist}(i^{\prime},i)=\overrightarrow{\rm dist}(i,i^{\prime})$ is verified
similarly. Since ${\tt
ENV}_{t^{\prime}}(\Gamma_{1}(i^{\prime}))\in{\mathcal{F}}_{{\textrm{FIH}}}$
while ${\tt ENV}_{t^{\prime}}(\Gamma_{1}(i^{\prime\prime}))\in{\overline{\cal
F}}_{{\textrm{FIH}}}$ for every $i^{\prime\prime}\neq i^{\prime}$ satisfying
${\rm dist}(i,i^{\prime\prime})\leq{\rm dist}(i,i^{\prime})$, we have that
${\tt ENV}_{t^{\prime}}(i^{\prime}-1)\neq{\tt ENV}_{t^{\prime}}(i^{\prime})$
while ${\tt ENV}_{t^{\prime}}(i^{\prime})={\tt
ENV}_{t^{\prime}}(i^{\prime}+1)={\tt ENV}_{t^{\prime}}(i^{\prime\prime})$ for
every $i^{\prime\prime}$ as above. This implies that ${\tt ENV}_{t}(i)={\tt
ENV}_{t^{\prime}}(i^{\prime})$ if $\textsf{parity}({\rm
dist}(i^{\prime},i))=0$ and ${\tt ENV}_{t}(i)\neq{\tt
ENV}_{t^{\prime}}(i^{\prime})$ otherwise.

  4. 4.

The function $h_{\rho}$ is defined as follows:
$h_{\rho}(\tau,\beta,\ell)=\tau$ if $\beta=0$ and it equals
$\overline{\tau}=\overline{\tau}_{1}\overline{\tau}_{2}\overline{\tau}_{3}$,
otherwise.

  5. 5.

Let $\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$ be a configuration and let $[x,y]$
be an interval of locations such that
$\sigma(\Gamma_{1}(x))\in{\mathcal{F}}_{\textrm{FIH}}$ and
$\sigma(\Gamma_{1}(y))\in{\mathcal{F}}_{\textrm{FIH}}$. We define the
configuration ${\widetilde{\sigma}}$ as follows. Let $i\in[(]n)$. If
$i\notin[x,y]$, we set ${\widetilde{\sigma}}(i)=\sigma(i)$. Otherwise, let
$j_{i}\in[x,y]$ be the location that minimizes ${\rm dist}(i,j)$ among the
locations for which $\sigma(\Gamma_{1}(j))\in{\mathcal{F}}_{\textrm{FIH}}$,
and set ${\widetilde{\sigma}}(i)=\sigma(j_{i})\oplus\textsf{parity}({\rm
dist}(i,j_{i}))$. In particular, note that if
$\sigma(\Gamma_{1}(i))\in{\mathcal{F}}_{\textrm{FIH}}$, then
${\widetilde{\sigma}}(i)=\sigma(i)$. We claim that for every $i\in[x,y]$ we
have that
${\widetilde{\sigma}}(\Gamma_{1}(i))\in{\mathcal{F}}_{\textrm{FIH}}$, and that
if $\sigma(\Gamma_{1}(i))\in{\mathcal{F}}_{\textrm{FIH}}$, then
${\widetilde{\sigma}}(i)=\sigma(i)$. Let $i\in[x,y]$. If
$\sigma(\Gamma_{1}(i))\in{\mathcal{F}}_{\textrm{FIH}}$, then $j_{i}=i$, and
hence either $\sigma(\Gamma_{1}(i-1))\in{\mathcal{F}}_{\textrm{FIH}}$ or
$\sigma(\Gamma_{1}(i+1))\in{\mathcal{F}}_{\textrm{FIH}}$, which implies that
either ${\widetilde{\sigma}}(i)\neq{\widetilde{\sigma}}(i-1)$ or
${\widetilde{\sigma}}(i)\neq{\widetilde{\sigma}}(i+1)$, and in both cases, it
holds that
${\widetilde{\sigma}}(\Gamma_{1}(i))\in{\mathcal{F}}_{\textrm{FIH}}$ and
${\widetilde{\sigma}}(i)=\sigma(i)$. If
$\sigma(\Gamma_{1}(i))\in{\overline{\cal F}}_{\textrm{FIH}}$, then, assume
without loss of generality that $j^{*}\in[i+1,y]$ (the case in which
$j^{*}\in[x,i-1]$ is similar). In this case, $j_{i}=j_{i+1}$, and hence
${\widetilde{\sigma}}(i)\neq{\widetilde{\sigma}}(i+1)$, which implies that
${\widetilde{\sigma}}(\Gamma_{1}(i))\in{\mathcal{F}}_{\textrm{FIH}}$.

  6. 6.

Assume that $\sigma(\Gamma_{1}(z))=000$ (the case that
$\sigma(\Gamma_{1}(z))=111$ is handled analogously). If
$\nu\oplus\gamma^{\prime}=0$, then we set $z^{\prime}=z+1$ and
${\widetilde{\sigma}}(z^{\prime}+1)=1$. Otherwise, we set $z^{\prime}=z+2$ and
${\widetilde{\sigma}}(z^{\prime})={\widetilde{\sigma}}(z^{\prime}+1)=1$. The
symmetric variant is established analogously.

###  10.2 Flip unless homogeneous