1
$\begingroup$

Toom's rule is a 2-dimensional cellular automaton which is known to have two distinct stationary measures in the thermodynamic limit, even after small perturbations to a probabilistic cellular automaton by introducing bit-flip or biased noise. What about more general local, but non-on-site noise. E.g., imagine after each step of the deterministic Toom's rule, flipping each pair of neighboring bits together, with a small constant probability. (This is well-defined since double-bit-flips commute with each other; if we want more general noise like low-probability CNOTs one would have to apply this noise in some kind of brick-layer-type manner.)

Is Toom's rule still stable under such more general noise? I assume there's nothing proven, but maybe there are numerical studies on this?

$\endgroup$

1 Answer 1

4
$\begingroup$

Toom's CA is robust under such noise. In fact, the class of noise distributions he considers is quite general. For a fixed CA $f$ on $\{0,1\}^{\mathbb{Z}^2}$ and a parameter $0 \leq \epsilon \leq 1$, let $M_\epsilon$ be the set of Borel probability measures $\mu$ on $(\{0,1\}^{\mathbb{Z}^2})^ {\mathbb{N}}$ such that every finite set $V \subset \mathbb{Z}^2 \times \mathbb{N}$ satisfies $$ \mu(\forall (\vec v, n) \in V : x(n+1)_{\vec v} \neq f(x(n))_{\vec v}) < \epsilon^{|V|} $$ for a $\mu$-random itinerary $x = (x(n))_{n \in \mathbb{N}} \in (\{0,1\}^{\mathbb{Z}^2})^ {\mathbb{N}}$. For $y \in \{0,1\}^{\mathbb{Z}^2}$, let $M_\epsilon(y)$ be the subset of those $\mu \in M_\epsilon$ with $\mu(x(0) = y) = 1$ (we fix the initial configuration instead of allowing it to be random). In Theorem 1 and Example 1 of [1], Toom proves that the north-east-self majority CA satisfies $$ \lim_{\epsilon \to 0} \sup_{\mu \in M_\epsilon(a^{\mathbb{Z}^2}), (\vec v, n) \in \mathbb{Z}^2 \times \mathbb{N}} \mu(x(n)_{\vec v} \neq a) = 0 $$ for $a = 0$ and $a = 1$. This means that the itinerary "remembers" its initial state if we store it in every cell, since every spacetime point has the same high probability of being in that state.

Intuitively, the marginals of the noise don't have to be independent or identically distributed at different spacetime points, as long as its error rate on any finite set of spacetime points is dominated by independent $\epsilon$-noise. In particular, choosing to independently flip adjacent pairs, or even larger local patterns, with a small enough probability on every time step results in a robust CA.

[1] A. Toom. Stable and Attractive Trajectories in Multicomponent Systems. Multicomponent Random Systems, Dekker, 1980, v. 6, pp.549-576. Originally published in Russian. Available at Toom's website.

$\endgroup$
3
  • $\begingroup$ Thanks for your answer. I'm coming from a different background and have trouble parsing it, hence a few basic questions: $\mu\in M_\epsilon$ is the probability distribution over different noise configurations, consisting of the space-time points where bit-flips occur, right? Or should I think of $\mu$ as a probability distribution over the space-time configurations of the noisy cellular automaton already? $\endgroup$
    – Andi Bauer
    Sep 27, 2021 at 21:48
  • $\begingroup$ Ok, I think the latter now. And then in your first equation $\mu(\ldots)<\epsilon^{|V|}$, the $\ldots$ is the set of space-time configurations which differ from those of $f$ on $V$? Am I getting that right? $\endgroup$
    – Andi Bauer
    Sep 27, 2021 at 21:55
  • 1
    $\begingroup$ @AndiBauer Yes, you're correct. You can think of $\mu(y)$ as a noisy or perturbed version of $f$ that produces a random itinerary (aka spacetime diagram) with initial state $y$. In the first equation, $\cdots$ is indeed the set of itineraries where the local rule of $f$ is not followed on any coordinate of $V$. The condition is that its probability decays exponentially with the size of $V$, but otherwise $\mu$ can have local and non-local correlations, and the positions of errors on each time step can even depend on the contents of the configuration. $\endgroup$ Sep 28, 2021 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.