Self-Replicating Structures in a Cellular Automata Space
Self-Replicating Structures in a Cellular Automata Space
Loading...
Files
Publication or External Link
Date
1998-10-15
Authors
Chou, Hui-Hsien
Advisor
Citation
DRUM DOI
Abstract
Biological experience and intuition suggest that self-replication is
an inherently complex phenomenon, and early cellular automata
self-replication models developed by computer scientists and
mathematicians supported that view. However, since von~Neumann's
original work in the 1950's, the study of cellular automata models of
self-replicating systems has progressively led to smaller and simpler
systems. This thesis demonstrates for the first time that it is
possible to create automatically self-replicating structures in
cellular automata models rather than, as has been done in the past, to
design them manually. These emergent self-replicating structures
employ a General Purpose Self-Replicating cellular automata rule set
which can support the replication of structures of different sizes and
their growth from smaller to larger ones. This thesis also
demonstrates that, by letting self-replicating structures carry
additional information besides replication instructions, they can be
used to solve computationally hard problems such as the Satisfiability
(SAT) problem. It is shown that self-replicating structures can be
made to carry characteristic codes and selection forces can be
implemented in cellular automata space. This study opens the door to
further studies that could lead to general, solution-evolvable
structures and truly self-programming systems.
(Also cross-referenced as UMIACS-TR-96-85)