Slow-Down in Universal Simulation

The article considers computing media (iterative structures) on lattices, and derives estimates for the slow-down that occurs in simulating a large class of media by one such medium. It is shown that the requirement of a guaranteed slow-down on the entire class of media with fixed input and output alphabets is not compatible with the requirement of element-by-element recoding of the initial state of the simulated medium to the initial state of the model (regular simulation). Examples of universal models with minimum possible guaranteed slow-down and examples of regular universal models are given.