Graph automata: Natural expression of self-reproduction

Kohji Tomita, Haruhisa Kurokawa, Satoshi Murata

Research output: Contribution to journalArticlepeer-review

44 Citations (Scopus)


A variety of models of self-reproduction process have been proposed since von Neumann initiated this field with his self-reproducing automata. Almost all of them are described within the framework of two-dimensional cellular automata. They are heavily dependent on or limited by the peculiar properties of the two-dimensional lattice spaces. But such properties are irrelevant to the essential nature of self-replication. In this paper, we introduce a new framework called "graph automata" to obtain a natural description of complicated spatio-temporal developmental processes such as self-reproduction. The most advantageous point of this methodology is that it is not restricted to particular lattice space. As an illustrative example, a self-reproduction of Turing machine, which requires very long description by conventional cellular automata, is shown in a simple and straightforward formulation. Graph automata provide a new tool to approach important scientific problems such as evolution of morphology, and also to give the basis of self-reproducing and self-repairing artifacts.

Original languageEnglish
Pages (from-to)197-210
Number of pages14
JournalPhysica D: Nonlinear Phenomena
Issue number4
Publication statusPublished - 2002 Nov 1


  • Cellular automata
  • Emergence
  • Self-organization
  • Self-reproduction
  • Turing machine


Dive into the research topics of 'Graph automata: Natural expression of self-reproduction'. Together they form a unique fingerprint.

Cite this