Chapter 5: 2 Dimensions And Beyond

By Xah Lee. Date:

Introduction p169.

Says that some phenomen of 2D and 3D does not happen in 1D. Knot is gives as example. This is a reason given to explore 2D and 3D CA. Says that in this chapter it will encounter many “specific effects that depen on having more than one dimension.”. Then, claims “… adding more dimensions does not ultimately seem to have much effect on the occurrence of behavior of any significant complexity”.

Cellular Automata p170.

2D and 3D simple CA

it is asserted that dimensions does not seems to effect the complexity of CA. That is, 1D CA can exhibit complex behavior just as easily in 2D or more D.

p172 several simple 2D CA are investigated. Not much info is shown. These CAs startngs with a single cell. Half of them exibit horizontal and vertical symmetries. A slice of their evolution is also shown, which is like a 1D CA with nested pattern or simple repeated patten. Another 2D CA is shown, and is said to approximate a circle with a particular starting partern. It is asserted that “And so it sees that there can be great complexity not only in the detailed arrangement of black and white cells in a two-dimensional cellular automaton pattern, but also in the voerall shape of the pattern”.

This section is very lousy and cursory and brushed away. Then, 2 examples of 3D CA is shown. The assertion is that “And in particular, the basic phenomenon of complexity does not seem to depend in any crucial way on the dimensionality of the system one looks at”.

In the last 2 chapters, hundreds of CA are shown, and apparently thousands systems are examed systematically. Here, only few are discussed then a claim is made.

Note that, Mathematica at the time can only generate static graphics (no live animation, rotation, or interactive sliders etc). For 2D CA, it's rather easy to illustrate their characters visually by a static image with history. But for 3D CA, static images are very limited. So, the incapabilities of Mathematica might have contributed to the meager discussion of 3D CA.

Also, 4D CA or higher dimensions are not mentioned at all.

Ant 2D CA

p184 Ant crawling CA is being called Turning Machines here. It goes like this: On a rectangular grid. Each cell is either black or white. A ant crawls around, starting at a cell. The ant has n states. The init condition is a grid with cells particularly colored and with the ant at one cell. A set of rules are given, that says when the ant is at what state and the cell of what color, the ant should move to a particular neighbor cell and the original cell should be colored what.

pictures of 5 such rules with a 5-state ant are shown, with evolution from 1k to 10k. A particular rule is shown to 500k steps. It's path tends to move towards 4 o'clock but otherwise seems random.

It is asserted that: “For Turning machines with two or three possible states, only repetitive and nested behavior normally seem to occur. With four states, more complex behavior is possibel, but it is still rather rare”

substitution systems and fractals

p187 Start with a grid. Each cell is subdivided into smaller cells. A rule set is given that specifies that a given colored cell shall change into the subdivided cells of specific colors. Pictures evolution of 9 such system is shown, basically all nested pattern (fractals like that of Sirpinski Triangle or Cube/sponge)

p189 a geometrical substitution system. Here, a square is given where inside the square is a arrow indicating direction. A rule specifies that this square in next generation will become two connected squares with particular directions. The init condition is a square. 2 such system's evolution are shown. One shows a dragon-curve like overall shape, the other kinda like inward growing claw. A extension of this systems is that the rule takes one geometric shape and transforms it into one or more copies of the original shape in different orientations. Fractal Snowflake is one example of such. Invariably, all such system generates nested pattern.

It is observed that in order to get complex behavior, one needs to get the shapes to interact with neighbors. In order to define neighbor, a grid system is used again. Each grid subdivides into 4 smaller cells with particular colors. The rule looks at the cell's neighbors to determine how the smaller cells should be colored. For some reason, the grid is considered toroidal (edges glued). 8 system's evoluton are shown. They show nested structures with chaotic overall placement.

networks system

consider a network with directed edges, where each node has two outgoing edges. (directed graphs) Start with a given such network, and the rule specifies how one of the outgoing edges should change destination. Also, the rule can also specifies such that a directed edge may have a new node embedded.

In general, the rule for such network system bascally states which subnetwork (subgraph) configuration should be replaced by what. The subnetwork can be node based or edge based. Care must be taken when the rule add or delete nodes or edges, because they may conflict around a neighborhood.

it is asserted that simple rules based on near neighbors produce network evolutions that exhibit repetitive behavior, and when rules that involve the node's neighbors's neighbors, then such system exhibit behaviors: “in many respects completely random”.

The initial incentive with network system is to get rid of the rigid underlying unchanging neighborhood in CA.

This section on network systems is quite confusedly written.

multiway system

constraint based systems

Here, instead giving a rule that specifies change, one instead specifies constraints the pattern must satisfy. For example, consider a array of cells of two colors. One can say that each cell must have a neighbor of different color. The possible patterns satisfies this constraint is the result.

p221 “Are there simple sets of constraints that can force complex patterns?” The book asserts no: “I turns out that in one-dimensional systems there are not. For in one dimension it is possible to prove that any local set of constraints that can be satisfied at all can always be satisfied by some simple and purely repetitive arrangement of colors”.

The above is quite fuzzy. It says that it is possible to prove, as opposed to i have a proof or it is easy to prove. And the wording does not clearly state that complex patterns are impossible, it just says that such can “…always be satisfied by simple…”.

It is also not clear from this impossibility prose whether it includes far neighbors 1D CA or n-colors 1D CA, or other simple program systems that can be considered as 1D.

p212 some constraint system are examed. These are 2-colors 2D rectangular grids with edges wrapped (toroidal), and the contraints specifies that a black cell should have certain number of black neighbors and white neighbors, and likewise a white cell. (diagnals are not included as neighbors) Pics of 25 such constraint systems are shown. It seems that a exhaustic search on all possible constraints have been done. (many such constraints will have no pattern, for example, a black cell must have 4 white neighbors, and a white cell must have 4 white neighbors).

p212 The book claims that “Most of the constraints are satisfied by a single patern, together with tis rotations and refelctions. In some cases, two distinct paterns are possible, and in a few cases, a nifinite set of patterns are possible. In all cases where the constraints can be satisfied at all, a simple repetitive pattern nevertheless suffices” .

need to see the notes.