Personally, I am curious if there is any cellular automaton that has something like 3-dimensional rotational symmetry. If our universe can be described by a cellular automaton, it isn't obvious to me how such a symmetry could arise, but I wouldn't be surprised if someone figured it out.

http://blog.stephenwolfram.com/2017/06/oh-my-gosh-its-covere...

HN discussion:

https://news.ycombinator.com/item?id=14458955

https://news.ycombinator.com/item?id=14468707

There's a thing called a "Garden of Eden" configuration that has no predecessors, which is impossible to get to from any other possible state.

For a rule like Life, there are many possible configurations that must have been created by God or somebody with a bitmap editor (or somebody who thinks he's God and uses Mathematica as a bitmap editor, like Stephen Wolfram ;), because it would have been impossible for the Life rule to evolve into those states. For example, with the "Life" rule, no possible configuration of cells could ever evolve into all cells with the value "1".

https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_autom...

For a rule that simply sets the cell value to zero, all configurations other than pure zeros are garden of eden states, and they all lead directly into a one step attractor of all zeros which always evolves back into itself, all zeros again and again (the shortest possible attractor loop that leads directly to itself).

There is a way of graphically visualizing that global rule state space, which gives insight into the behavior of the rule and the texture and complexity of its state space!

Andrew Wuensche and Mike Lesser published a gorgeous coffee table book entitled "The Global Dynamics of Cellular Automata" that plots out the possible "Garden of Eden" states and the "Basins of Attraction" they lead into of many different one-dimensional cellular automata like rule 30.

http://users.sussex.ac.uk/~andywu/gdca.html

The beautiful color plates begin on page 79 in the free pdf file:

http://users.sussex.ac.uk/~andywu/downloads/papers/global_dy...

I've uploaded the money shots to imgur:

http://imgur.com/gallery/s3dhz

Those are not pictures of 1-d cellular automata rule cell states on a grid themselves, but they are actually graphs of the abstract global state space, showing merging and looping trajectories (but not branching since the rules are deterministic -- time flows from the garden of eden leaf tips around the perimeter into (then around) the basin of attractor loops in the center, merging like springs (GOE) into tributaries into rivers into the ocean (BOA)).

The rest of the book is an atlas of all possible 1-d rules of a particular rule numbering system (like rule 30, etc), and the last image is the legend.

He developed a technique of computing and plotting the topology network of all possible states a CA can get into -- tips are "garden of eden" states that no other states can lead to, and loops are "basins of attraction".

Here is the illustration of "rule 30" from page 144 (the legend explaining it is the last photo in the above album). [I am presuming it's using the same rule numbering system as Wolfram but I'm not sure -- EDIT: I visually checked the "space time pattern from a singleton seed" thumbnail against the illustration in the article, and yes it matches rule 30!]

http://imgur.com/a/lKAbP

"The Global Dynamics of Cellular Automata introduces a powerful new perspective for the study of discrete dynamical systems. After first looking at the unique trajectory of a system's future, an algoritm is presented that directly computes the multiple merging trajectories of the systems past. A given cellular automaton will "crystallize" state space into a set of basins of attraction that typically have a topology of trees rooted on attractor cycles. Portraits of these objects are made accessible through computer generated graphics. The "Atlas" presents a complete class of such objects, and is inteded , with the accompanying software, as an aid to navigation into the vast reaches of rule behaviour space. The book will appeal to students and researchers interested in cellular automata, complex systems, computational theory, artificial life, neural networks, and aspects of genetics."

https://en.wikipedia.org/wiki/Attractor

"Basins of attraction in cellular automata", by Andrew Wuensche:

http://onlinelibrary.wiley.com/doi/10.1002/1099-0526(200007/...

"To achieve the global perspective. I devised a general method for running CA backwards in time to compute a state's predecessors with a direct reverse algorithm. So the predecessors of predecessors, and so on, can be computed, revealing the complete subtree including the "leaves," states without predecessors, the so-called “garden-of-Eden" states.

Trajectories must lead to attractors in a finite CA, so a basin of attraction is composed of merging trajectories, trees, rooted on the states making up the attractor cycle with a period of one or more. State-space is organized by the "physics" underlying the dynamic behavior into a number of these basins of attraction, making up the basin of attraction field."

Pencil drawing from the very early days before automatic computer drawing was perfected:

http://www.ddlab.com/r30Pencil.gif

If you like the book, you'll love the code!

http://www.ddlab.com/

http://www.ddlab.com/screensave3.png

http://uncomp.uwe.ac.uk/wuensche/2006_ddlab_slides1.pdf

http://uncomp.uwe.ac.uk/wuensche/meta.html

http://uncomp.uwe.ac.uk/wuensche/boa_idea.html

http://uncomp.uwe.ac.uk/wuensche/downloads/papers/2008_dd_ov...

This doesn't appear to be true for arbitrarily many digits, and I'm struggling to see how the two fields may even be connected. Some properties appear similar, eg. the Möbius function, too, appears to sum up to 0.

Meanwhile the major tech corps would kill for that kind of bang per buck.

(More seriously, don’t confuse O() with Ω() and Θ(), folks: https://en.wikipedia.org/wiki/Big_O_notation.)

    I. Convergent uniform final state
    II.  Convergent simple pattern final state
    III. "Random"
    IV. "Complexity"

Later, Wolfram self-published "A New Kind of Science" (ANKoS). ANKoS is abysmal and barely readable but, from what I can understand from what little I read of it, Wolfram updated his understanding and instead basically classified CA into two categories, either 'simple' or 'complex', where, again, 'complex' means Turing Machine Equivalent.

If I remember correctly, I think Wolfram even used Rule 30 as a basis for random number generators somewhere (Mathematica?).

Considering the tenor of the problems, maybe Wolfram is still essentially classifying CA into his four initial categories as it looks like he's pushing for the idea that "Rule 30 == 'random'".

My personal take on this is that the idea that there are basically "two" classifications of CA, either 'simple' (non-Turing Machine equivalent) and 'complex' (Turing Machine equivalent) is correct. Though it might be the case where the more 'random' a CA looks, the harder it is to do the reduction to TME, maybe even going so far as having a diverging reduction cost.

Regardless, this is why these questions might be interesting. Is Rule 30 TME? If so, then that answers question 3 (O(n) simulation is essentially saying there's no "shortcut" and you're basically doing full computation). Questions 1 and 2 are, in my opinion, shades of the same TME question, where non-periodic is another way of saying there's no short-circuit computation and calculating the average is getting at the unpredictability (read 'required computability') of the cells.

If Rule 30 isn't TME but still requires O(n) cost to predict, that's also pretty interesting as it requires as much computing power to predict it but isn't as powerful as a Turing Machine. From a broader perspective, this gets at the whole "randomness vs. determinism" idea, as this is a deterministic system that, for many purposes, behaves randomly. This idea is probably old news to this crowd but there's a close link to TME and randomness that is still not completely understood and investigations into CA of this sort are another way to tackle this idea.

[1] https://www.amazon.com/Cellular-Automata-Complexity-Collecte...

[2] https://en.wikipedia.org/wiki/Turing_machine_equivalents

[3] https://www.wolframscience.com/nks/p231--four-classes-of-beh...

From a different engineering perspective, Dave Ackley had some interesting things to say about the difficulties of going from 2D to 3D, which I quoted in an earlier discussion about visual programming:

https://news.ycombinator.com/item?id=18497585

David Ackley, who developed the two-dimensional CA-like "Moveable Feast Machine" architecture for "Robust First Computing", touched on moving from 2D to 3D in his retirement talk:

https://youtu.be/YtzKgTxtVH8?t=3780

"Well 3D is the number one question. And my answer is, depending on what mood I'm in, we need to crawl before we fly."

"Or I say, I need to actually preserve one dimension to build the thing and fix it. Imagine if you had a three-dimensional computer, how you can actually fix something in the middle of it? It's going to be a bit of a challenge."

"So fundamentally, I'm just keeping the third dimension in my back pocket, to do other engineering. I think it would be relatively easy to imaging taking a 2D model like this, and having a finite number of layers of it, sort of a 2.1D model, where there would be a little local communication up and down, and then it was indefinitely scalable in two dimensions."

"And I think that might in fact be quite powerful. Beyond that you think about things like what about wrap-around torus connectivity rooowaaah, non-euclidian dwooraaah, aaah uuh, they say you can do that if you want, but you have to respect indefinite scalability. Our world is 3D, and you can make little tricks to make toruses embedded in a thing, but it has other consequences."

Here's more stuff about the Moveable Feast Machine:

https://news.ycombinator.com/item?id=15560845

https://news.ycombinator.com/item?id=14236973

The most amazing mind blowing demo is Robust-first Computing: Distributed City Generation:

https://www.youtube.com/watch?v=XkSXERxucPc

And a paper about how that works:

https://www.cs.unm.edu/~ackley/papers/paper_tsmall1_11_24.pd...

Plus there's a lot more here:

https://movablefeastmachine.org/

Now he's working on a hardware implementation of indefinitely scalable robust first computing:

https://www.youtube.com/channel/UC1M91QuLZfCzHjBMEKvIc-A

The PDF is here: http://users.sussex.ac.uk/~andywu/downloads/papers/global_dy...

But you can apply simple transformations on rules, like reflecting them (1D and 2D) and rotating them (2D only), or layering them (having a bunch of lower dimension rules running in parallel). Or you can perform a 1D rule along each horizontal/vertical axis (or even diagonal axis) and then combine them somehow (like XOR). But that will typically have a vastly different behavior.

One of my favorite 2D rules that looks kind of like an animated version of Rule 30 is "HGLASS", named that because it looks kind of like the falling sand in an hourglass. If you run it in a torus (edges wrap around), it tends to settle into a circular dependency tree with gaps bubbling up through it like space between cars in a traffic jam.

https://www.fourmilab.ch/cellab/manual/rules.html#HGlass

This is a five-neighbor two-state two-dimensional cellular automaton found at random by Margolus and Toffoli. It organizes a nice sliding flow on a random screen, and it disassembles solid starting patterns in an interesting way.

You can see it here:

https://donhopkins.com/home/CAM6/

1. Click the gray square in the upper right corner.

2. Click "Rules".

3. Select from the Rule dropdown "von Neumann HGlass Down".

4. Draw in the cells.

5. Click in the histogram at to to change the drawing cell value. Click "Tools" to configure the drawing tool.

6. Play around with the other variants of HGLASS (Up/Down/Left/Right, echo, heat) and parallel rules like 4 HGlass Down / All)

EDIT: Oh I understand now! Each generation is 1D. Thanks for explaining! :D