Self-reproduction in asynchronous cellular automata

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

    29 Citations (Scopus)
    38 Downloads (Pure)

    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.
    Original languageEnglish
    Title of host publicationProcs of the 2002 NASA/DOD Conf on Evolvable Hardware (EH'02)
    PublisherInstitute of Electrical and Electronics Engineers (IEEE)
    Pages201-209
    Volume2002
    ISBN (Print)0-7695-1718-8
    Publication statusPublished - 2002

    Fingerprint

    Dive into the research topics of 'Self-reproduction in asynchronous cellular automata'. Together they form a unique fingerprint.

    Cite this