Cellular Automata are Generic

Nachum Dershowitz
Evgenia Falkovich

Any algorithm (in the sense of Gurevich's abstract-state-machine axiomatization of classical algorithms) operating over any arbitrary unordered domain can be simulated by a dynamic cellular automaton, that is, by a pattern-directed cellular automaton with unconstrained topology and with the power to create new cells. The advantage is that the latter is closer to physical reality. The overhead of our simulation is quadratic.

In Ugo Dal Lago and Russ Harmer: Proceedings Tenth International Workshop on Developments in Computational Models (DCM 2014), Vienna, Austria, 13th July 2014, Electronic Proceedings in Theoretical Computer Science 179, pp. 17–32.
Published: 10th April 2015.

ArXived at: http://dx.doi.org/10.4204/EPTCS.179.2 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org