University of Hertfordshire

Self-reproduction in asynchronous cellular automata

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Documents

  • 902237

    Final published version, 309 KB, PDF document

View graph of relations
Original languageEnglish
Title of host publicationProcs of the 2002 NASA/DOD Conf on Evolvable Hardware (EH'02)
PublisherIEEE
Pages201-209
Volume2002
ISBN (Print)0-7695-1718-8
Publication statusPublished - 2002

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.

ID: 432796