On the limit set of some universal cellular automata

AbstractIn this paper we construct a simulation of a Turing machine by cellular automata based on the equivalence between programmable machines and Turing machines. For this class of cellular automata we prove that the associated limit language is regular. We also introduce algebraic characteristics which reduce the study of the complexity of the limit language to the analysis of a class of one-symbol languages