## Abstract

Building on the work of Von Neumann, Burks, Codd, and

Langton, among others, we introduce the first examples of

asynchronous self-reproduction in cellular automata. Reliance

on a global synchronous update signal has been a

limitation of all solutions since the problem of achieving

self-production in cellular automata was first attacked by

Von Neumann half a century ago. Our results obviate the

need for this restriction.

We introduce a simple constructive mechanism to transform

any cellular automata network with synchronous update

into one with the same behavior but whose cells may be

updated randomly and asynchronously. This is achieved by

introduction of a synchronization substratum which locally

keeps track of the passage of time in a local neighborhood

in a manner that keeps all cells locally in-step.

The generality of this mechanism is guaranteed by a general

mathematical theorem (due to the author) that allows

any synchronous cellular automata configuration and rule

to be realized asynchronously in such a way the the behavior

of the original synchronous cellular automata can

be recovered from that of the corresponding asynchronous

cellular automaton. Thus all important results on selfreproduction,

universal computation, and universal construction,

and evolution in populations of self-reproducing

configurations in cellular automata that have been obtained

in the past carry over to the asynchronous domain.

Langton, among others, we introduce the first examples of

asynchronous self-reproduction in cellular automata. Reliance

on a global synchronous update signal has been a

limitation of all solutions since the problem of achieving

self-production in cellular automata was first attacked by

Von Neumann half a century ago. Our results obviate the

need for this restriction.

We introduce a simple constructive mechanism to transform

any cellular automata network with synchronous update

into one with the same behavior but whose cells may be

updated randomly and asynchronously. This is achieved by

introduction of a synchronization substratum which locally

keeps track of the passage of time in a local neighborhood

in a manner that keeps all cells locally in-step.

The generality of this mechanism is guaranteed by a general

mathematical theorem (due to the author) that allows

any synchronous cellular automata configuration and rule

to be realized asynchronously in such a way the the behavior

of the original synchronous cellular automata can

be recovered from that of the corresponding asynchronous

cellular automaton. Thus all important results on selfreproduction,

universal computation, and universal construction,

and evolution in populations of self-reproducing

configurations in cellular automata that have been obtained

in the past carry over to the asynchronous domain.

Original language | English |
---|---|

Title of host publication | Procs of the 2002 NASA/DOD Conf on Evolvable Hardware (EH'02) |

Publisher | Institute of Electrical and Electronics Engineers (IEEE) |

Pages | 201-209 |

Volume | 2002 |

ISBN (Print) | 0-7695-1718-8 |

Publication status | Published - 2002 |