Cellular automata and complexity

What Hacker News says

1. saretiredJun 2016
   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.

   thread
2. abetuskOct 2019
   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...

   Show morethread
3. billswiftAug 2009
   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.
   thread