# Does any algorithm exist for computing the state of a non-trivial cellular automaton after an arbitrary number of time steps?

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?

• 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). – Draconis Jul 1 '19 at 22:05
• @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?" – John L. Jul 2 '19 at 5:02
• @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.) – Draconis Jul 2 '19 at 5:06
• 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. – John L. Jul 2 '19 at 6:01
• @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? – Reggie Simmons Jul 2 '19 at 6:08