Linear Cellular Automata and Decidability

We delineate the boundary between decidability and undecidability in the context of one-dimensional cellular automata. The key tool for decidability results are automata-theoretic methods, and in particular decision algorithms for automatic structures, that are inherently limited to dealing with a bounded number of steps in the evolution of a configuration. Undecidability and hardness, on the other hand, are closely related to the full orbit problem: does a given configuration appear in the orbit of another?