If have a cellular automaton, can I see the state of the board after something like $10^{{10}^{10}}$ time steps? For trivial cases, this is possible - for example, a cellular automaton where the state of the board is known to repeat after some finite period.

But are there any cellular automata (or perhaps even similar computational structures) that display chaotic behavior but can also be very quickly evaluated to extreme time steps into the future?

  • 3
    $\begingroup$ Depends on the automaton. Some cellular automata are Turing complete, for example, which means you can't prove whether they'll ever repeat a state (for certain initial conditions). $\endgroup$ – Draconis Jul 1 '19 at 22:05
  • $\begingroup$ @Draconis, have you proved that "you can't prove whether a Turing-complete machine will ever repeat a state for certain initial conditions"? Do you actually mean "there is no algorithm to determine whether a Turing-complete machine on an input will ever repeat a state?" $\endgroup$ – John L. Jul 2 '19 at 5:02
  • $\begingroup$ @Apass.Jack Indeed—more precisely, I mean "given a Turing machine and its initial conditions, no algorithm can always determine in finite time whether it will ever repeat a state" where "state" encompasses the tape as well. (The non-provability point is also true, but for different reasons.) $\endgroup$ – Draconis Jul 2 '19 at 5:06
  • $\begingroup$ If an automaton can be evaluated very quickly to arbitrary extreme time steps into the future by an algorithm, it is reasonable to say its behavior is not chaotic. Or do you mean "never repeating" (aperiodic) by "chaotic"? Please clarify. $\endgroup$ – John L. Jul 2 '19 at 6:01
  • $\begingroup$ @Apass.Jack From my understanding, "chaotic" simply refers to a system highly sensitive to it's initial conditions. Can you elaborate as to why a system sensitive to initial conditions could not be evaluated quickly to extreme time steps into the future? $\endgroup$ – Reggie Simmons Jul 2 '19 at 6:08

Two answers...

  • There is a trivial algorithm to do it: "Just" run the automaton for the required steps.
  • No, there is no general way to compress the computation. If you can prove that the automaton enters a periodic configuration, you certainly can. You can also precompute the result of a certain number of steps, and use that to skip ahead (doing several steps in one round). That is one of the ideas used to speed up finding Busy Beavers. But in general, as cellular automata are Turing-complete, to find out if you are in one of the cases where it stops or repeats is easily seen to be undecidable.
| cite | improve this answer | |

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.