OCA:Rule 120

From LifeWiki
Revision as of 03:58, 22 December 2023 by DroneBetter (talk | contribs) (corrections and clarifications, simplify k(p) formula (it seems I forgot about the very simplest modular arithmetic identity when I found it in miscellaneous curiosities), add (inelegant and caseworky but complete) proof of solution to bitwise recurrence for o(k))
Jump to navigation Jump to search


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 120 (or W120) is a 2-state 1D cellular automaton. It is notable as a class 4 rule, and for the slow growth it exhibits from the initial state of two adjacent on-cells.

Rule 225 is its black/white reversal, and exhibits the same behaviour from a one-cell state, upon inverting the background.

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 120 evolution is as follows:

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

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

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 of 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.)

Rule 120, and rule 225 from the inverted state onwards, together with their reflections, form the unique range-1 rules that exhibit Θ(√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 % denote the modulo function.

Let ¬, ∧, ⊕ and ∨ denote bitwise NOT, AND, XOR and OR, and ≪ and ≫ denote bitwise shift (n≪i = ⌊n*2i⌋ and n≫i = ⌊n2i⌋). Per [1], we have the descending order of precedence (-,¬),(*,/,%),(+,-),(≪,≫),(∧),(⊕),(∨) (the first two being single-input functions, negation and NOT). Unlike Python, shifts can be by negative amounts.

Per [2], define functions on the binary representation of n; let λ(n) = ⌊log2(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 'bitwise inflation' function bn, that returns a number whose base-2n representation is the base-2 representation of its input (ie. b2(6) = 20, since 6 = 1102 and 20 = 1104). We have that lim supk->∞(bn(k)kn)=1 (with equality at powers of 2), and lim infk->∞(bn(k)kn)=12n-1 (with records preceding powers of 2).

Generalisations

Since the perturbation is aligned to the rightwards diagonal, 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 on." 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 ∑2n+1-2k=2n-1(2k) = (22n2).

The rule emulating it upon the background state inversion is defined

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

given by rule integer ∑2n+1-1k=2n+1(2k) + 1 = (22n-1)2.

align right left neighbourhood width
stable inverting stable inverting
n=2 120 225 106 169 3
sum ∑2n+1-2k=2n-1(2k) ∑2n+1-1k=2n+1(2k) + 1 ∑2n-1k=1(4k)+22n+1-2 ∑2n+1k=3(4k)+1 n+1
form (22n2) (22n-1)2 5*22n+1-812 22n+1-106

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 log2 of the period of the kth-rightmost cell) and d(k) (returning the log2 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) = ∨ .nj=1(o(k-j)) + 1

The solution to which has the exact form

o(k) = 2*(2n-1)*bn(⌊kn+1⌋) + { 1 . . . . . . . . . . . . . .k ≡ n (mod n+1)2*(1+2k%(n+1)-2n)*2ρ(⌊kn+1⌋)*n .else
Proof:

In this form, the expressions to determine whether the ith bit of each term of o(k) is 1 are

2*(2n-1)*bn(⌊kn+1⌋)≫i∧1 = ⌊kn+1⌋≫⌊i-1n⌋∧1

the term in cases is negative, so requires two's complement,

{ 1 . . . . . . . . . . . . . .k ≡ n (mod n+1)2*(1+2k%(n+1)-2n)*2ρ(⌊kn+1⌋)*n .else }≫i∧1 = { i = 0 . . . . . . . . . . . . . . . .k ≡ n (mod n+1)i-1-ρ(⌊kn+1⌋)*n ∈ {0,k%(n+1)}∪[n,∞) .else

and together,

2*(2n-1)*bn(⌊kn+1⌋) + { 1 . . . . . . . . . . . . . .k ≡ n (mod n+1)2*(1+2k%(n+1)-2n)*2ρ(⌊kn+1⌋)*n .else }≫i∧1 = { k ≡ n (mod n+1) . . . . . . . . . . . . . . . . . . . . i = 0{ (i-1)%n = k%(n+1) . k%(n+1)<n and ⌊i-1n⌋ = ρ(⌊kn+1⌋)⌊kn+1⌋≫⌊i-1n⌋&1 . .else .else

using the recurrence relation,

o(k)-1≫i∧1 = ∨ .nj=1(o(k-j))≫i∧1 = { k !≡ n (mod n+1) . . . . . . . . . . . . . . . . . i = 0∨ .nj=1({(i-1)%n = (k-j)%(n+1) . (k-j)%(n+1)<n and ⌊i-1n⌋ = ρ(⌊k-jn+1⌋)⌊k-jn+1⌋≫⌊i-1n⌋&1 . . . .else}) .else

Computing o(k)-1 symbolically, for the i ≠ 0 case,

We consider the case in which k ≡ n (mod n+1)
o(k)-1≫i∧1 = ∨ .nj=1({(i-1)%n = (k-j)%(n+1) . ⌊i-1n⌋ = ρ(⌊k-jn+1⌋)⌊k-jn+1⌋≫⌊i-1n⌋&1 . . . .else})
⌊k-jn+1⌋ = ⌊kn+1⌋, (k-j)%(n+1)<n is always true, and since (k-j)%(n+1) = k-j it passes through all values between 0 and n-1 exactly once, (i-1)%n = (k-j)%(n+1) is true for one OR-summand
o(k)-1≫i∧1 = (⌊i-1n⌋ = ρ(⌊kn+1⌋) or ⌊kn+1⌋≫⌊i-1n⌋∧1)
the former condition implies the latter, since for a bit's index to be the 2-adic valuation, it must be the lowest 1-bit. Thus this case's form is correct if all n preceding terms abided by the other case's
the last bit is set to 1 by the increment at the end
and in which k !≡ n (mod n+1)
since the 1-bits in the preceding k-j ≡ n (mod n+1) case are a strict superset of the 1-bits of the terms with k-j preceding it (since there can be at most n-1 of the n 'inflated' bits in the most recent bn carry index contained before it), the OR-sum need only be considered for j ≤ k%(n+1) + 1
o(k)-1≫i∧1 = ∨k%(n+1) + 1j=1({i%n = (k-j)%(n+1) . (k-j)%(n+1)<n and ⌊in⌋ = ρ(⌊k-jn+1⌋)⌊k-jn+1⌋≫⌊in⌋&1 . . .else})
substituting j = k - j,
o(k)-1≫i∧1 = ∨k-1j=⌊kn+1⌋*(n+1)-1({i%n = j%(n+1) . j%(n+1)<n and ⌊in⌋ = ρ(⌊jn+1⌋)⌊jn+1⌋≫⌊in⌋&1 .else})
splitting the first iteration apart,
o(k)-1≫i∧1 = ⌊kn+1⌋-1≫⌊in⌋&1 ∨ ∨k-1j=⌊kn+1⌋*(n+1)({i%n = j%(n+1) . ⌊in⌋ = ρ(⌊jn+1⌋)⌊jn+1⌋≫⌊in⌋&1 .else})
in the remaining iterations, there exists a j such that i%n = j%(n+1) iff i%n < k%(n+1), and in all other cases, the fact that ⌊jn+1⌋ = ⌊kn+1⌋ enables it to be substituted to an also-iterationless form
o(k)-1≫i∧1 = ⌊kn+1⌋-1≫⌊in⌋&1 ∨ {i%n < k%(n+1) . ⌊in⌋ = ρ(⌊kn+1⌋)⌊kn+1⌋≫⌊in⌋&1 .else
the last bit of this OR is set to 1 by the preceding k ≡ n (mod n+1) case, and since bn(x) ∨ bn(y) = bn(x ∨ y), bitwise ORing (2n-1)*bn(⌊kn+1⌋-1) with (2n-1)*bn(⌊kn+1⌋) (albeit with the new lowest 1-bit being carried to only partially 'filled') will result in all bits up to the preceding term's lowest 1-bit being filled, causing the present term to increment to a new bit in the inflated bit, 'filling' it further.
o(k)-1≫i∧1 = (⌊in⌋ < ρ(⌊kn+1⌋)) ∨ {i%n < k%(n+1) . ⌊in⌋ = ρ(⌊kn+1⌋)⌊kn+1⌋≫⌊in⌋&1 .else

End proof.

The other functions have elementary forms also,

p(k) = { 0. . . . . . . . . . . . . . . . . . . . . . . . . . . k < n1. . . . . . . . . . . . . . . . . . . . . . . . . . . k = n⌊log2(⌊kn+1⌋)⌋*n + 1 + min(n,k+1-(n+1)*2⌊log2(⌊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∧2p(k)-1 ≥ o(k) and (k%(n+1)<n and ⌊kn+1⌋∧⌊kn+1⌋-1 = 0 or f(k-(n+1≪λ(⌊kn+1⌋)-1),t) = 1)0 . . . . . else

Other functions

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

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

Where the number of times a cell turns on during its period is given by ⌊2c(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.

Note that the "density" of the kth cell (the proportion of generations for which it's on) is then given by

{ 1 . . . . . . .k < n2d(k)+c(k)-p(k). else

Bounds

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

  • k < n,
  • k is of the form (n+1)*2j
  • n = 1

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

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

See also

  • sqrt replicator rule, an outer-totalistic rule containing a replicator emulating a 4-state isotropic rule which admits similar methods of analysis.

References

  1. ↑ Python, operator precedence
  2. ↑ Donald Knuth, The Art of Computer Programming, Pre-Fascicle 1A, Draft of Section 7.1.3
Retrieved from "https://conwaylife.com/w/index.php?title=OCA:Rule_120&oldid=143548"