One-dimensional cellular automaton/Wolfram rule

The Wolfram rules (or elementary cellular automata) are a family of one-dimensional cellular automata studied by Stephen Wolfram in the 1980's, in which (similarly to Life and INT and MAP rules) a cell's state in each iteration is determined by the rule as a function of the state of each cell in its neighbourhood in the preceding iteration.

A width-n neighbourhood has n cells, so 2ⁿ possible configurations of cells. Similarly to MAP rules, Wolfram rules are anisotropic, and specify each transition (the resultant state from a neighbourhood configuration) as a bit of a 2ⁿ-bit number, the rule integer (that ranges from 0 to 2^2ⁿ-1 inclusive). In the Wolfram code, the ith bit of the rule integer (the digit in its binary representation of magnitude 2ⁱ) determines a cell's subsequent state when the initial neighbourhood state, interpreted as a binary number, is i. Usually, the term "Wolfram rule" is used to refer to one of the 256 possible rules for n=3.

Generally, n is odd, but when it's even, for each resultant cell to be at the centre of its neighbourhood and remain aligned, states in alternate generations can be represented in staggered lines like a brick wall. Any width-n rule may be encoded to a width-n+1 rule by concatenating its rule integer with a copy of itself.

Similarly to Life, statements about their Turing-completeness refer to the ability of finite patterns on an infinite tape to perform arbitrary computations. However, often 2-dimensional cellular automata have structures that can act as 'analogue simulations' at 1 1D iteration per 2D iteration, allowing properties of the parent rule to be proven by considering the simpler behaviour of the emulated one within finite tapes.^{[n 1]} The capability for a finite pattern in any rule to emulate an initially-finite pattern in an infinite tape in rule 110 is sufficient to prove it to be Turing-complete.

Enumeration and equivalence classes

While there are 2^2ⁿ rules, dualities (and thus equivalence classes) exist similarly to their 2-dimensional counterpart. A rule's black/white reversal is obtained by taking the bitwise NOT of its rule integer then reversing the order of its 2ⁿ bits.^{[n 2]} For a rule to be invariant under black/white reversal (self-complementary), each bit of the right half of its integer must be the NOT of the corresponding bit on the left side, so each of the cycles is comprised of a pair of transitions. There are 2^n-1 of them, and 2^{2^n-1} such rules. Left/right reflection is done by moving each bit at index i to the index given by the reversal of i's binary representation (over bit length n). Rules invariant under this are isotropic, and because cycles are either pairs of asymmetric transitions or single symmetric ones, there exist (2ⁿ+2^⌈n/2⌉)/2 cycles.^{[n 3]}

Similarly to the INT and MAP rulespaces, each rule corresponds with an alternating pair of rules that act as its strobing dual, which are identical if the original one is self-complementary, and are equivalent to either reversing its binary representation or NOT'ing each bit, and analogously to the checkerboard dual, each transition of a self-complementary rule may have its index in the rule integer XORed with one of alternating 1's and 0's, to define a rule equivalent to alternating the states of every other cell in both the initial and output state, such that patterns simulated in one act as perturbations in an infinite checkerboard in the other.

Similarly to MAP rules, these divide the self-complementary rules into computationally-equivalent pairs, and the subset that are isotropic further into quartets, however here neither are considered because both are affected by boundary conditions and affect oscillatory periods.

If rules that can be converted to each other by the dualities of reflection and black/white reversal are considered equivalent, using the Pólya enumeration theorem, there are precisely (2^2ⁿ+2^{(2ⁿ+2^⌈n/2⌉)/2}+2^{2^n-1+n%2})/4 equivalence classes, where ⌈⌉ denotes the ceiling operator and % the modulo operator. For n=3, this provides 88.^[2]

Table of equivalence classes for `n=3`

Here, invariance types are:

N: None. (4 members)
S: Symmetrical but not self-inverse. (2 members)
I: Self-inverse but not symmetrical. (2 members)
O: Both self-inverse and symmetrical. (1 member)
A: Equivalent to its black/white reversal when reflected. (2 members)

As a brief summary, in Wolfram's classification,

Class-1 rules eventually lead to all cells being dead,
Class-2 rules lead to simple ash of still lifes and oscillators,
Class-3 rules exhibit chaotic and aperiodic growth,
Class-4 rules are in between 2 and 3, and are the easiest to engineer (so the primary candidates for proving Turing-completeness).

Expressions are provided for computation in terms of C bitwise operators, in the same bracket level the operators ~&^| (NOT, AND, XOR, OR) are evaluated in descending order of precedence.^[3] p is the left cell, q the central one and r the right one. In languages with arbitrarily long integers (like Python), given a state s, unbounded tapes may be simulated with p=s; q=s<<1; r=s<<2.

OEIS sequences given are defined such that a(n)'s binary representation is the state of the central perturbation after n iterations from a single cell in an infinite empty tape, and some are shared across multiple nonequivalent rules (which behave differently with different initial states).

The generating function for a rule r is a fraction of multivariate polynomials over x and y, such that the coefficient of x^k*yⁿ in their series expansion is the state of the cell k cells rightwards from the initial single cell after n iterations. Note that many also have univariate functions provided in their OEIS sequences, where the coefficient of tⁿ is the binary expansion of the nth row.


equivalence class (strobing?)		rules, duals (strobing, checkerboard)			bitwise expression for first member	OEIS seq. of states from single cell	multivariate generating function in `GF(2)`	Turing-complete?	Wolfram classification	Notes
N	n	2,16,191,247			`r&~(p\|q)`	A266180		No	2
		6,20,159,215			`~p&(q^r)`	A266180, A010684		No	2
		8,64,239,253			`q&r&~p`	A000007		No	1
		10,80,175,245			`r&~p`	A000302		No	2
		12,68,207,221			`q&~p`	A000079		No	2
		14,84,143,213			`~p&(q\|r)`			No	2
		24,66,189,231			`(p^q)&(p^r)`			No	2
		26,82,167,181			`p^(r\|p&q)`	A038183			2	Single cell becomes Sierpinski, soups become leftwards-moving bands of different power-of-2 periods resembling Sierpinskis
		28,70,157,199			`p^(q\|p&r)`	A001045		No	2
		30,86,135,149			`p^q\|r`	A110240			3	Behaves chaotically from single bit, is used by Mathematica as a random number generator, its leftwards-moving edge has a growing periodic section
		34,48,187,243			`r&~q`			No	2
		38,52,155,211			`q^(r\|p&q)`			No	2
		42,112,171,241			`r&~(p&q)`			No	2
		44,100,203,217			`(q\|r)&(p^q)`	A000079		No	2
		46,116,139,209			`p^(q\|p^r)`			No	2
		56,98,185,227			`(p\|r)&(p^q)`			No	2
		58,114,163,177			`q^(p\|q^r)`			No	2
		60,102,153,195			`p^q`	A117998	`11-(x+1)*y`	No	3	Distributive with XOR, ie. r60(a) XOR r60(b) = r60(a XOR b), emulates width-2 rule 6
		62,118,131,145			`r&~p\|p^q`			No	2	Soups produce agars of diagonal lines with towers and misalignments moving c/2 rightwards that consume the towers
		74,88,173,229			`(q\|r)&(p^r)`			No	2
		78,92,141,197			`p^(r\|p^q)`			No	2
		106,120,169,225			`r^p&q`				4	Leftward-moving lines interact in a Sierpinski-like manner (a single on cell in rule 225 grows with `Θ(√n)`), part of infinite family of higher-range rules
		110,124,137,193			`q&~p\|q^r`	A117999		Yes^[4]	4
		130,144,190,246			`r&~(p^q)`	A037576		No	2
		134,148,158,214			`(q\|r)&(p^q^r)`	A118171		No	2
		136,192,238,252			`q&r`	A000225		No	1
		138,174,208,244			`r&(q\|~p)`			No	2
		140,196,206,220			`q&(r\|~p)`	A000079, A000225		No	2
		152,188,194,230			`q^r^(p\|q\|r)`	A118173		No	2
		154,166,180,210			`r^p&~q`	A038183			2	Similar to rule 26 but with solid regions
		162,176,186,242			`r&(p\|~q)`			No	2
		168,224,234,248			`r&(p\|q)`			No	1
		172,202,216,228			`q^p&(q^r)`	A000079,		No	2
		40,96,235,249			`r&(p^q)`			No	1
	y	3,17,63,119			`~(p\|q)`	A266069		No	2
		7,21,31,87			`~(p\|q&r)`			No	2
		9,65,111,125			`~(p\|q^r)`			No	2
		11,47,81,117			`~p&(r\|~q)`			No	2
		13,69,79,93			`~p&(q\|~r)`			No	2
		25,61,67,103			`~(p&q\|q^r)`				2	Random soups produce agars, in which perturbations move at different speeds
		27,39,53,83			`~q^r&(p^q)`			No	2
		35,49,59,115			`~q&(r\|~p)`			No	2
		41,97,107,121			`~(p&q\|p^q^r)`				2	Random soups become agars containing crawlers in opposite directions
		45,75,89,101			`p^(q\|~r)`				3	Chaotic like rule 30 but strobing, left edge (which also has a leading periodic section) grows at c/2
S	n	0,255			`0`			No	1
		4,223			`q&~(p\|r)`	A000079		No	2
		18,183			`~q&(p^r)`	A038183			3
		22,151			`p^q^r^(p&q&r)`				3
		32,251			`p&r&~q`			No	1
		36,219			`(p^q)&(q^r)`	A000079		No	2
		50,179			`~q&(p\|r)`	A002450		No	2
		54,147			`q^(p\|r)`	A118108		Conjectured^[5]	4	Complex agar interactions
		72,237			`q&(p^r)`			No	2
		76,205			`q&~(p&r)`	A000079		No	2
		90,165			`p^r`	A038183	`11-(x+1x)*y`	No	3	Distributive with XOR
		94,133			`q&~p\|p^r`	A118101		No	2
		104,233			`p^q^r^(p\|q\|r)`			No	2
		108,201			`q^p&r`	A000079		No	2
		122,161			`p&~q\|p^r`				3
		126,129			`p^q\|p^r`				3	From single cell produces Sierpinski instead of checkerboard, but in soups, becomes equivalent to that of rule 122, because isolated cells don't emerge
		128,254			`p&q&r`	A083420		No	1
		132,222			`q&~(p^r)`	A000079, A083420		No	2
		146,182			`(p\|r)&(p^q^r)`	A038183			3
		160,250			`p&r`			No	1
		164,218			`p^r^(p\|q\|r)`	A000079, A038183		No	2
		200,236			`q&(p\|r)`	A000079		No	2
	y	1,127			`~(p\|q\|r)`			No	1
		5,95			`~(p\|r)`	A266176		No	2
		19,55			`~(q\|p&r)`			No	2
		33,123			`~(q\|p^r)`			No	2
		37,91			`~(p&q\|p^r)`			No	2
		73,109			`~(p&q\|p^q^r)`				2	2 adjacent on cells surrounded by off cells comprise indestructible walls, between which there is periodic Sierpinski behaviour, is chaotic without them
I	y	15,85	s	c	`~p`			No	2
	n	170,240	s	c	`r`			No	2
	y	43,113	s	c	`~p^(p^q)&(q^r)`			No	2
	n	142,212	s	c	`p^(p^q\|p^r)`			No	2
O	n	232	s	c	`(p\|q)&(r\|p&q)`			No	2
	y	23	s		`~((p\|q)&(r\|p&q))`			No	2
	n	178	s		`p^(p^r)&(q^r)`			No	2
	y	77	s		`~p^(p^r)&(q^r)`			No	2
	n	204	s	c	`q`	A000079		No	2
	y	51	s	c	`~q`			No	2
	n	150	s	c	`p^q^r`		`11-(x+1+1x)*y`	No	3
	y	105	s	c	`~p^q^r`	A038184		No	3
A	n	156,198			`q^(p&~r)`			No	2
	n	184,226			`p^q&(p^r)`			No	2
	y	29,71			`~r^q&(p^r)`			No	2
	y	57,99			`q^(p\|~r)`			No	2

Notes

↑ For instance, b34kz5e7c8s23-a4ityz5k's rule 150 emulator allowed Jiahao Yu to prove its omniperiodicity.^[1]
↑ This is because, given n, a rule r, its bit length l=2ⁿ, and a transition i, in r's black/white dual (r'), the transition when a neighbourhood's state is i's bitwise NOT (~i) will be the opposite of the value of the ith bit of r, which is thus NOT'ed and moved to the index w-1 & ~i, which (where 0 ≤ i < w) is w + ~i = w-1-i.
↑ This is the number of length-n tapes under action of reversal, A005418(n+1)= A361870(1,n).

References

↑ yujh (February 1, 2022). Re: B34kz5e7c8/S23-a4ityz5k (!) (discussion thread) at the ConwayLife.com forums
↑ The particular value 88 is also noted in page 57 of Stephen Wolfram's A New Kind of Science (2002)
↑ For rules not reduced by equivalence classes, see the table in A New Kind of Science (online version) notes, ch. 3, sec. 2; Rule expressions [for cellular automata] (and c's 2008 errata, with the minimal forms, showing that all 3-input 1-output logic gates may be implemented in no more than 5 such basis gates) and the tables in DroneBetter's Wolfram rule simulator, ankos is a transcription of that to Python and alpha is from WolframAlpha's stored minimal forms (that contain on average about 0.136 fewer logic gates per rule).
↑ Matthew Cook (2004), Universality in Elementary Cellular Automata (explains cyclic tag systems and their Turing-completeness, and how structures from agar crawlers in rule 110 can emulate them)
↑ Genaro Juárez Martínez, Andrew Adamatzky, Harold V. McIntosh (April 1, 2006), Chaos, Solitons & Fractals, vol. 28. iss. 1; Phenomenology of glider collisions in cellular automaton Rule 54 and associated logical gates

External links

Elementary cellular automaton at Wikipedia
Elementary cellular automaton at Wolfram Mathworld

Other tables (more extensive than this)

OEIS wiki, Index to Elementary Cellular Automata
Stephen Wolfram, Cellular Automata and Complexity: Collected Papers, 1994 (Westview Press, ISBN: 0-201-62716-7), p. 516-521; Tables of Cellular Automaton Properties
DroneBetter, Wolfram e.g.f.'s

[2] For instance, b34kz5e7c8s23-a4ityz5k's rule 150 emulator allowed Jiahao Yu to prove its omniperiodicity.^[1]

[3] This is because, given n, a rule r, its bit length l=2ⁿ, and a transition i, in r's black/white dual (r'), the transition when a neighbourhood's state is i's bitwise NOT (~i) will be the opposite of the value of the ith bit of r, which is thus NOT'ed and moved to the index w-1 & ~i, which (where 0 ≤ i < w) is w + ~i = w-1-i.

[4] This is the number of length-n tapes under action of reversal, A005418(n+1)= A361870(1,n).

[1] yujh (February 1, 2022). Re: B34kz5e7c8/S23-a4ityz5k (!) (discussion thread) at the ConwayLife.com forums

[5] The particular value 88 is also noted in page 57 of Stephen Wolfram's A New Kind of Science (2002)

[6] For rules not reduced by equivalence classes, see the table in A New Kind of Science (online version) notes, ch. 3, sec. 2; Rule expressions [for cellular automata] (and c's 2008 errata, with the minimal forms, showing that all 3-input 1-output logic gates may be implemented in no more than 5 such basis gates) and the tables in DroneBetter's Wolfram rule simulator, ankos is a transcription of that to Python and alpha is from WolframAlpha's stored minimal forms (that contain on average about 0.136 fewer logic gates per rule).

[7] Matthew Cook (2004), Universality in Elementary Cellular Automata (explains cyclic tag systems and their Turing-completeness, and how structures from agar crawlers in rule 110 can emulate them)

[8] Genaro Juárez Martínez, Andrew Adamatzky, Harold V. McIntosh (April 1, 2006), Chaos, Solitons & Fractals, vol. 28. iss. 1; Phenomenology of glider collisions in cellular automaton Rule 54 and associated logical gates

[n 1]

[n 2]

[n 3]

[2]

[3]

[4]

[5]

[1]

One-dimensional cellular automaton/Wolfram rule

Contents

Enumeration and equivalence classes

Table of equivalence classes for `n=3`

Notes

References

External links

Navigation menu

One-dimensional cellular automaton/Wolfram rule

Enumeration and equivalence classes

Table of equivalence classes for n=3

Notes

References

External links

Navigation menu

Search

Table of equivalence classes for `n=3`