I think it's possible to build things whose behavior is indeterminate. For a smple example, consider program designed to forcast weather. You can describe all the cogs and wheels of the program, all the functions, objects, operators, but you cannot predict its output because you cannot predict its input.
Moving along to a more complex program, the mythical AI program, It would also have as its primary "object", creating an optimal response to a predicted future. To achieve even the level of a cat brain would require processing power we only dream about. And once again, to make predictions about the behavior of the catbot, you would have to have continuous access to its entire internal state, plus all its inputs. In short, the predictive device would have to parallel the device being predicted. This is equivalent to attempting to predict some arbitrary future state of your automata without running the program. Even worse, the grid on which the automata operates is not flat and unchanging. It is being changed continuously by other automata that are hidden from our spacetime perspective.