Does any algorithm exist for computing the state of a non-trivial cellular automaton after an arbitrary number of time steps?
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.