People have tried to explain the universe with cellular automata and so far none of these systems has even been consistent with our current observations of the universe, let alone predicting some new behavior that would allow us to prove or disprove that the theory was true. (If your theory doesn't predict anything new, it's not a new theory at all!)
Requiring infinite recursion of cellular automata would seem to make the whole problem much harder...