HN Books @HNBooksMonth

For some context, Wolfram published a book of collected papers called "Cellular Automata and Complexity" [1] where he classified Cellular Automata (CA) into four broad categories:

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

Where "Complexity" essentially means Turing Machine Equivalent [2]. See also [3].

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

My information is pretty dated but I found Wolfram's collected papers a very good read (Amazon lists it as ~$40 but you can get it for under $5 used) [1]. I wouldn't be surprised if you could find a torrentable version as well.

You have to be careful about what kind of cellular automata you're talking about. There's the 'toy models' such as 1d and 2d cellular automata that Wolfram and Conway's Game of Life [2] fall into but there's also many others, including lattice gases and more complex modeling options. I assume you mean the cellular automata that have the flavor that Wolfram and Conway are talking about.

The linked Wolfram book is a 'classical' treatment where he introduces different classes (I,II,III and IV) of cellular automata, ranging from completely ordered (1d, rule 0, say) to completely disordered (1d, rule 32, say).

I hope I'm not rambling too much but from what I understand it was a commonly accepted that 'complexity happens at the edge of chaos' [2]. Wolfram's "A New Kind of Science" (again, from my understanding) essentially represents an evolving view (by Wolfram) where he graduates from "complexity happens at the edge of chaos" to "complexity is the norm, rather than the exception". Wolfram coins this as the "principle of computational equivalence" [3]. People have recommended ANKoS and I would really recommend against reading it. I think the principle of computational equivalence and the proof that rule 110 is Turing complete (given in ANKoS) are interesting but they're so buried in exceptionally bad writing as to be not worth the effort.

If you're interested in studying Conway's Game of Life [4] more, there's Golly [5], which is a wonderful piece of software. Cellular automata is a very large field and there are lots of different questions to ask about it, so you might want to limit your scope if you want more directed suggestions.

As a sort of tangential recommendation, I would highly encourage you to check out "Complexity and Criticality" by Christensen and Moloney [6]. Though they don't talk about the cellular automata that are described above, they motivate a lot of the different concepts of criticality, phase transitions and other motifs that show up repeatedly when discussing these models and others like them.

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

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

[3] http://mathworld.wolfram.com/PrincipleofComputationalEquival...

[4] https://en.wikipedia.org/wiki/Conway's_Game_of_Life

[5] http://golly.sourceforge.net/

[6] https://www.amazon.com/Complexity-Criticality-Advanced-Physi...

⬐ saretired

Wolfram has put the entire text of Cellular Automata and Complexity: Collected Papers online

http://www.stephenwolfram.com/publications/cellular-automata...

The survey papers in this collection would be the place for OP to start; note that some of the other papers assume a significant background in mathematics and physics.

Wolfram's 1994 book "Cellular Automata and Complexity" (http://www.amazon.com/Cellular-Automata-Complexity-Collected...) covered most of the same ground as NKS, but was a collection of papers and was a lot more readable; even it was almost 600 pp.