OCA:Rule 120

Rule 225
x=0, y = 0, rule = W120 ! #C [[ THEME Inverse ]] #C [[ RANDOMIZE2 RANDSEED 1729 THUMBLAUNCH THUMBNAIL THUMBSIZE 2 GRID ZOOM 6 WIDTH 600 HEIGHT 600 LABEL 90 -20 2 "#G" AUTOSTART PAUSE 2 GPS 8 LOOP 256 ]] LifeViewer-generated pseudorandom soup
Number	120
Computation	p⊕¬(q∨r)
Character	Class 4
Black/white reversal	120
Left/right reflection	169

Wolfram's Rule 225 (or W225) is a 2-state 1D cellular automaton. It is notable as a class 4 rule, and for the slow growth it exhibits from the single-on-cell state.

Definition

As in all elementary cellular automata, whether a cell in the pattern will be 0 or 1 in the new generation depends on its current value, as well as those of its two neighbours.

The Rule 225 evolution is as follows:

Current pattern	111	110	101	100	011	010	001	000
New state for center cell	1	1	1	0	0	0	0	1

The name of the rule, as in all elementary cellular automata, is the binary sequence of the new states (11100001); If interpreted as a binary number, its denary representation is 225.

From the initial state of a single on-cell perturbation in an infinite tape of off-cells (from which Stephen Wolfram simulated the evolution, in investigating all 256 rules), the on-cell's neighbourhood becomes off, but the off-cells elsewhere all change state to on. Thereafter, it emulates the behaviour its dual, rule 120 (computed as p⊕q∧r), from a pattern of three adjacent on-cells at generation 1. (The unique finite predecessor state at generation 0 has two on-cells.)

From this state onwards, it is the unique range-1 rule that exhibits Θ(√t) growth. Consider the function l(t) (that returns the pattern's length on the tth iteration), then there are the bounds lim infn->∞(l(t)√t) = √3√2 and lim supn->∞(l(t)√t) = 3√2.

Bitwise functions

Let ¬, ∧, ⊕ and ∨ denote bitwise NOT, AND, XOR and OR, and ≪ and ≫ denote bitwise shift.

Per , define functions on the binary representation of n; let λ(n) = ⌊log₂(n)⌋ + 1 be the length, ρ(n) be the number of trailing 0s (the exponent of the highest power of 2 dividing n, or the 2-adic valuation of n), and ν(n) be the number of 1s (the Hamming weight of n), equivalently

ρ(0)=0; ρ(2*n)=ρ(n)+1, ρ(2*n+1)=0 . . . (A007814)

λ(0)=0; λ(2*n)=λ(n)+1, λ(2*n+1)=λ(n)+1. (A029837)

ν(0)=0; ν(2*n)=ν(n), . ν(2*n+1)=ν(n)+1. (A000120)

Consider the function b_n, that returns a number whose base-2ⁿ representation is the base-2 representation of its input (ie. b₂(6) = 20, since 6 = 110₂ and 20 = 110₄). We have that lim supk->∞(b_n(k)kⁿ)=1 (with equality at powers of 2), and lim infk->∞(b_n(k)kⁿ)=12ⁿ-1 (with records preceding powers of 2).

Generalisations

Since the perturbation is right-aligned, one can shift it left by one cell each iteration, then it has the equivalent description "each cell flips its state if all of the 2 cells to its right are off." Fix an integer n ≥ 1, then consider the n cells to its right instead of 2. This is described by the rule in the width-n+1 neighbourhood equivalent to

f(s) = s ⊕ ¬ ∨ .ni=1(s≪i)

for which the rule integer is ∑2ⁿ⁺¹-1k=2ⁿ+1(2^k) + 1 = (2²ⁿ-1)².

Upon the background state inversion, it instead emulates

f(x) = s ⊕ ∧ .ni=1(s≪i)

given by rule integer ∑2ⁿ⁺¹-2k=2ⁿ-1(2^k) = (2²ⁿ2).

In this emulated rule, n+1 cells are on in generation 1, uniquely finitely preceded by the generation-0 state in which n cells are on. Hereafter, "on" and "off" will refer to states in the emulated rule.

Since each cell's period is a factor of the lcm of those of the cells to its right, then multiplied by 2 if these cells all turn on simultaneously an odd number of times, by induction all cells' periods are powers of 2. Consider the functions p(k) (returning the log₂ of the period of the kth-rightmost cell) and d(k) (returning the log₂ of the gcd of the durations for which the cell remains in a fixed state).

The function l(t) is slow-growing, so consider its inverse function, o(k), which returns the first generation at which the kth cell turns on. The other two functions have the equivalent characterisations p(k)=λ(o(k)) and d(k)=ρ(o(k)).

o(k) = 0 for all k < n, and thereafter abides by the bitwise recurrence relation

o(k) = ∨ .ni=1(o(k-i)) + 1

The solution to which has the exact form

o(k) = 2*(2ⁿ-1)*b_n(⌊kn+1⌋) + 2^{ρ(⌊kn+1⌋)*n}*{ 1 . . . . . . . . . . . . . .k ≡ n (mod n+1)2*(1+2^k%(n+1)-2ⁿ)*2^{ρ(⌊kn+1⌋)*n . else}

The other functions have elementary forms

p(k) = { 0. . . . . . . . . . . . . . . . . . . . . . . . . . . k < n1. . . . . . . . . . . . . . . . . . . . . . . . . . . k = n⌊log₂(⌊kn+1⌋)⌋*n + 1 + min(n,k+1-(n+1)*2^{⌊log₂(⌊kn+1⌋)⌋}) . k > n

and

d(k) = { 0. . . . . . . . . . . . . . . k < n or (a:=ρ(i:=⌊kn+1⌋ + ⌊k+1n+1⌋)) = 0n*(a-1) + 1 + k - ⌊(n+1)*i2⌋ . else

The state of the kth cell at the tth iteration is given by the function

f(k,t) = { 1 . . . . . k < nt≫d(k)∧1 . . . t∧2^p(k)-1 ≥ o(k)0 . . . . . else

Other functions

Since p is a strictly increasing function, it has a floor-inverse. The first cell whose period is 2^p has index

k(p) = { 0 . . . . . . . . . . . . . . . . . . . . . . p = 0n . . . . . . . . . . . . . . . . . . . . . . p = 1(n+1)*(2^⌊p+n-2n⌋-1)+3*(n-1)2 + p - ⌊p+n-2n⌋*n .else

Where the number of times a cell turns on during its period is given by ⌊2^c(k)⌋,

c(k) = { -1 . . . . . . . . . . . k < n.1 . . . . . . . . . . .(a:=λ(i:=⌊k+1n+1⌋*2-1)-ρ(i)-ν(i)) = 0.n*a - k + ⌊(n+1)*i+n2⌋. else

For the n=1 case (in which the rule produces successive rows of the Sierpinski triangle), this is equivalent to λ(k) - ρ(k) - ν(k), the number of non-trailing 0s in k's binary representation (A086784(k)), and for other n, it is obtained by a sequence morphism, from enacting the following steps upon A086784

• Multiply each element by n
• For all pairs of consecutive elements x,y with x > y, insert x-1,x-2,...,y+1 between them to conserve the property that for all k, c(n,k) ≥ c(n,k-1)-1.
• For all triplets of consecutive elements x,y,z all equal to 0, replace y with n consecutive 0s.

Bounds

2*(kn+1)ⁿ ≤ o(k), with equality where k

• < n,
• is of the form (n+1)*2^j
• is even (this condition pertains only if n = 1)

and lim supk->∞(o(k)kⁿ) = 2*(2ⁿ-1)(n+1)ⁿ (with records occurring where k is of the form (n+1)*2^j + n).

Since 2(n+1)ⁿ ≤ o(k)kⁿ < 2*(2ⁿ-1)(n+1)ⁿ and λ(s(o(k))) = max(n,k), λ(s(t)) ∈ Θ(ⁿ√t), with bounds (n+1)*ⁿ√tⁿ√2*(2ⁿ-1) < λ(s(t)) ≤ (n+1)*ⁿ√tⁿ√2.