Suppose the parameters/inputs of the computation include the time at which the configuration of a particular deterministic chaotic system needs to be computed.

Say, for instance, as input we have a start configuration of the chaotic Rule 30 cellular automata and a time-step $t$, and as output, we require the configuration at time-step $t$.

What can be said about the computational complexity of such a computation?


Wolfram's rule 30 is a one dimensional cellular automaton. If you want to know the state of the CA at step $t$, given the initial configuration, you just need to run the rule for $t$ steps. At every step the computation consist in no more than a bunch of if's, so the time complexity of such CA is linear in $t$.

| cite | improve this answer | |
  • $\begingroup$ Ahhh yes of course, can we do better? $\endgroup$ – pkwssis Oct 18 '19 at 11:08
  • $\begingroup$ @pkwssis I strongly doubt it, but I don't know if anyone ever prooved it formally. If you want to expand your knowledge on cellular automatons, I strongly recommend that you read the book "A New Kind of Science" written by Wolfram himself. $\endgroup$ – Yamar69 Oct 18 '19 at 11:13
  • 1
    $\begingroup$ This answer is not quite right; the running time is actually quadratic in $t$, as explained in the link in my comment above. The reason is that you need to simulate up to $t$ cells. Thus, simulating a single step takes $O(t)$ time, not $O(1)$ time. Multiply that by $t$ steps, and you get $O(t^2)$ time. As explained in the link I provided, it is an open question whether we can do substantially better. $\endgroup$ – D.W. Oct 18 '19 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.