Asynchronous cellular automaton

Cellular automata, as with other multi-agent system models, usually treat time as discrete and state updates as occurring synchronously.

The synchronous approach assumes the presence of a global clock to ensure all cells are updated together.

A general method repeatedly discovered independently (by K. Nakamura in the 1970s, by T. Toffoli in the 1980s, and by C. L. Nehaniv in 1998) allows one to emulate exactly the behaviour of a synchronous cellular automaton via an asynchronous one constructed as a simple modification of the synchronous cellular automaton (Nehaniv 2002).

As a consequence, it follows immediately from results on synchronous cellular automata that asynchronous cellular automata are capable of emulating, e.g., Conway's Game of Life, of universal computation, and of self-replication (e.g., as in a Von Neumann universal constructor).

Bersini and Detours (1994) have shown how sensitive Conway's Game of Life is to the updating scheme.

Harvey and Bossomaier (1997) pointed out that stochastic updating in random boolean networks results in the expression of point attractors only: there is no repeatable cyclic behaviour, although they introduced the concept of loose cyclic attractors.

Sipper et al. (1997) investigated the evolution of non-uniform CAs that perform specific computing tasks.