University of Hertfordshire

Self-reproduction in asynchronous cellular automata

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

Standard

Self-reproduction in asynchronous cellular automata. / Nehaniv, C.L.

Procs of the 2002 NASA/DOD Conf on Evolvable Hardware (EH'02). Vol. 2002 IEEE, 2002. p. 201-209.

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

Harvard

Nehaniv, CL 2002, Self-reproduction in asynchronous cellular automata. in Procs of the 2002 NASA/DOD Conf on Evolvable Hardware (EH'02). vol. 2002, IEEE, pp. 201-209.

APA

Nehaniv, C. L. (2002). Self-reproduction in asynchronous cellular automata. In Procs of the 2002 NASA/DOD Conf on Evolvable Hardware (EH'02) (Vol. 2002, pp. 201-209). IEEE.

Vancouver

Nehaniv CL. Self-reproduction in asynchronous cellular automata. In Procs of the 2002 NASA/DOD Conf on Evolvable Hardware (EH'02). Vol. 2002. IEEE. 2002. p. 201-209

Author

Nehaniv, C.L. / Self-reproduction in asynchronous cellular automata. Procs of the 2002 NASA/DOD Conf on Evolvable Hardware (EH'02). Vol. 2002 IEEE, 2002. pp. 201-209

Bibtex

@inproceedings{cf6cac1b22ea40a8a122347682916412,
title = "Self-reproduction in asynchronous cellular automata",
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.",
author = "C.L. Nehaniv",
year = "2002",
language = "English",
isbn = "0-7695-1718-8",
volume = "2002",
pages = "201--209",
booktitle = "Procs of the 2002 NASA/DOD Conf on Evolvable Hardware (EH'02)",
publisher = "IEEE",

}

RIS

TY - GEN

T1 - Self-reproduction in asynchronous cellular automata

AU - Nehaniv, C.L.

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

M3 - Conference contribution

SN - 0-7695-1718-8

VL - 2002

SP - 201

EP - 209

BT - Procs of the 2002 NASA/DOD Conf on Evolvable Hardware (EH'02)

PB - IEEE

ER -