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