Cellular automata and time T

yes, the time step of such cellular automaton would be a different time than the one in our universe. It depends of you definition of universe, but it is outside our physical realm in the same sense that the internal time in a computer virtual would be is. We can run the simulation at any pace, with or without interruptions, or even backwards. The "beings" inside the simulation would still experience a continuous time. A nice article on the subject is "pigs in cyberspace" by Hans Moravec. You 'll find it online.

The time in our universe would obviously be intimately linked to the CA-time, but I feel there is an important nuance here that I haven't seen properly adressed; The smallest possible amount of time in the "real" universe would correspond to a single generation of the CA, so that any amount of "work" or calculation required to update the CA a single step adds nothing to the "real" time of the process. For instance, there are CA algorithms that can factor integers in polynomial generations. If you run such an algorithm on a computer, the algorithm has to spend time computing every cell, and thus cannot finish in polynomial time. However, the same algorithm implemented directly in the CA fabric of the universe, should be able to factor integers in polynomial time. My hunch is that something like this explains the expected performance of quantum computers.