Chapter 6: Starting From Randomness

By Xah Lee. Date:

the emergence of order p223

p223. to p230. Showing some pictures and discussion of CA that started from random init condition, basically leading the reader to the “4 classes of behavior” starting on p231.

four classes of behavior p231

1. almost uniform. 2. simple structure or repeat. 3. random-like, but with small structures (For example, triangles) 4. Mixture of order and randomness; has localized structures.

this imprecise classification is compared to the classification of solid/liquid/gas, or living organism into plants and animals, saying that there will be borderline cases.

p240. 4 examples of borderline cases are given: totalistic involving nearest neighbors and 3 possible colors for each cell. Code: 219, 438, 1380, 1632.

p240. asserts that the only way to find out about a class is pretty much run it. And, “it is often the case that rules which occur next to each other in some sequence have similar behavior”. This assertion is backed up by one page of CA examples on p241.

p242. Asserts that different classes also happen in continuous CA (p155). 10 examples are shown in p243 and 3 examples of local structures are shown in p244.

needs to study the rules on how the strips are rid of

p249: find out how the pict on left is produced. The game of life is given code as “outer totalistic 9-neighbor code 224”. Find out this numbering scheme.

p245: 2D CA's behavior can also be grouped into 4 classes. In particular a method of observation is to graph the history of a slice.

sensitivity to initial conditions p250

systems of limited size and class 2 behavior p255

randomness in class3 systems p261

special initial conditions p266

the notion of attractors p275

structures in class 4 systems p281

p250 “sensitivity to init conditions”. For class 1 and 2 its not interesting. For class 3, a change in one init cell spread in a uniform way. For class 4, a cell change in init cond spread sporadically. Basically, a change in init condition behaves the same as the class's overall behavior. (as if the init cond is one single cell) This can be characterized as how one change in init cell communicates how far. For class 1 and 2, no communication. For 3, communicates. For 4, unpredicable.

p255: “systems of limited size and class 2 behavior”: “…it is then a general result that any ssytem of limited size that involves discrete elements and follows definite rules must always eventually exhibit repetitive behavior.” For example, rule 110 seems to become class 2 behavior if the its grid is just 900 with left and right connected.

essentially, once a 1D CA's grid's left and right sides are connected, it become periodic. The max period is number of possible states raised to nth power, where n is grid size. For 2-colo 1D CA, that's 2^n. One now studies the relation of period with its size change. The period in general changes somewhat sporadically as a function of grid size. Of all elementary 1D CA, only rule 45 seems to retain the max possible period (2^n). Rule 110's period stays quite low regardless of size increase, seems to be roughly n^3.

Question: did Stephen Wolfram actually have carried out the period/size study for all 1D CA? or was it selected cases?

p261 “randomness in class 3 system”. Class 3 is characterized by random triangles, when started with random init cond, however, nested struct when start with single cell. Here we study where this randomness come from. For rule 22, randomness seems intrinsic. For rule 90, it needs a random init cond to get a random behavior.

Question: is there a exhaustive experiment on all the 256 basic 1D CA on randomness? (or, just the class 3 ones)

p267: class 3 CAs, when given a concocted input, can produce class 2 behavior. …in any CA it is inevitable that init cond which consist just of a fixed block of cells repeated will lead to simple repetitive behavior. Each block essentiall acts lie a system of limited size. “And in fact it turns out to be quite common for there to exist special init cond for one CA that make it behave just like other CA”.

p270: self emulation. certain CA can emulate itself. For example, in rule 90's graph, consider a block of 4 cells as one unit (and just look at the upper left corner), it becomes the graph of rule 90 itself with fewer steps. In general, many CA can have self emulation property.


CA can be run on rectangular grids, but also triangular grids or honeycomb grids, each one with different connections. In general, CA can run on networks. (i.e. as in graph theory) The nodes can be finite or infinite, regularly laied out or not. As to regularly laied out grids of infinit nodes as in plane or 3D struts, we step into the theories of topological classifications of regular tilings.

Question: in the above definition… how does one reconcile the concept of dimensions, i.e. 2D vs 3D? For example, in 2D, we have arbitrary regular tilings as the grid, for example, honeycomb. And more regular structs in 3D. Viewed as a network, what makes a network 2D or 3D?

Besides photos, are all the illustrations in ANKOS produced in Mathematica?