Simulation limitations of affine cellular automata

This paper contributes to the formalization of the computational capacity of cellular automata by developing the notion of simulation (automaton \(A\) is said to be simulated by automaton \(B\) if each space-time or orbit diagram of \(A\) can be reproduced by \(B\) up to suitable transformations). The abstract ideas are applied to affine automata, and the main result is that most affine automata over a finite field can only simulate affine automata over the same field. This in particular strengthens known results on limits to the computational capacity of linear automata. More generally the results allow the notion of simulation to be formalized using language from universal algebra. This shows how, for example, some of the results here are consequences of deeper results due to \textit{J. D. H. Smith} [Mal'cev varieties. Berlin-Heidelberg-New York: Springer-Verlag (1976; Zbl 0344.08002)] and \textit{H. P. Gumm} [Algebra Univers. 9, 8--34 (1979; Zbl 0414.08002)] about abelian algebras with a Mal'tsev term and provides additional tools and perspectives with which to study the simulation capacity of other classes of automata.

Recommendations

Cites work

This page was built for publication: Simulation limitations of affine cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6549671)