Skip to main content
Typo in result
Source Link
Ilkka Törmä
  • 740
  • 1
  • 5
  • 12

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) = 1 $$$$ \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.

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) = 1 $$ 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.

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.

Source Link
Ilkka Törmä
  • 740
  • 1
  • 5
  • 12

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) = 1 $$ 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.