Computing by Temporal Order: Asynchronous Cellular Automata

Michael Vielhaber
(Hochschule Bremerhaven, Germany)

Our concern is the behaviour of the elementary cellular automata with state set 0,1 over the cell set Z/nZ (one-dimensional finite wrap-around case), under all possible update rules (asynchronicity).

Over the torus Z/nZ (n<= 11),we will see that the ECA with Wolfram rule 57 maps any v in F_2^n to any w in F_2^n, varying the update rule.

We furthermore show that all even (element of the alternating group) bijective functions on the set F_2^n = 0,...,2^n-1, can be computed by ECA57, by iterating it a sufficient number of times with varying update rules, at least for n <= 10. We characterize the non-bijective functions computable by asynchronous rules.

In Enrico Formenti: Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires (AUTOMATA&JAC 2012), La Marana, Corsica, September 19-21, 2012, Electronic Proceedings in Theoretical Computer Science 90, pp. 166–176.
Published: 13th August 2012.

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