Why can't we generate the output of cellular automata at time step t without first generating all the preceding states? Why can we do this for some functions? What features of a function does it relate to? Is it about whether it can be graphed as a line or a curve? Why can't we come up with a function that takes in a cellular automata ruleset and a timestep t and gives us the output in constant time with respect to t?
6
-
$\begingroup$ Can you generate the output of cellular automata at time step t without first generating all the preceding states? $\endgroup$– John L.Commented Jun 14, 2019 at 19:27
-
$\begingroup$ Because "one of these rules is Turing-complete". Wait, although I believe that logic/intuition is correct, I have not understood it fully yet. $\endgroup$– John L.Commented Jun 14, 2019 at 19:36
-
1$\begingroup$ You can try applying the time hierarchy theorem to get a time lower bound for specific Turing-complete rules. $\endgroup$– Yuval FilmusCommented Jun 15, 2019 at 10:32
-
$\begingroup$ You can do this for some cellular automata. For example, try predicting the output of the Wolfram elementary CA rules 204, 240, 254, 60 or 150 after $t$ steps. I think you'll be able to find some shortcuts... $\endgroup$– Ilmari KaronenCommented Jun 15, 2019 at 10:53
-
$\begingroup$ "Why can't we come up with a function that takes in a cellular automata ruleset and a timestep t and gives us the output in constant time with respect to t?" Because, in constant time, you can't even read the value of $t$. $\endgroup$– David RicherbyCommented Jun 15, 2019 at 10:56
|
Show 1 more comment