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 |