Graph automata: natural expression of self-reproduction
K. Tomita, H. Kurokawa, S. Murata
Physica D 171, 197, 2002.
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.