Problem Solving During Artificial Selection of Self-Replicating Loops

Hui-Hsien Chou and James A. Reggia. Physica D 115:293–312, 1998.

Past cellular automata models of self-replication have generally done only one thing: replicate themselves. However, it has recently been demonstrated that such self-replicating structures can be programmed to also carry out a task during the replication process. Past models of this sort have been limited in that the program involved is copied unchanged from parent to child, so that each generation of replicants is executing exactly the same program on exactly the same data. Here we take a different approach in which each replicant receives a distinct partial solution that is modified during replication. Under artificial selection, replicants with promising solutions proliferate while those with failed solutions are lost. We show that this approach can be applied successfully to solve an NP-complete problem, the satisfiability problem. Bounds are given on the cellular space size and time needed to solve a given problem, and simulations demonstrate that this approach works effectively. These and other recent results raise the possibility of evolving self-replicating structures that have a simulated metabolism or that carry out useful tasks.

Keywords: self-replication, self-organization, cellular automata, SAT problem, artificial selection.

Cellular Automata Models of Self-Replicating Systems

James A. Reggia, Hui-Hsien Chou and Jason D. Lohn. In Marvin Zelkowitz, editor, Advances in Computers, vol. 47, Academic Press, New York, 1998.

Since von Neumann's seminal work around 1950, computer scientists and others have studied the algorithms needed to support self-replicating systems. Much of this work has focused on abstract logical machines (automata) embedded in two-dimensional cellular spaces. This research has been motivated by the desire to understand the basic information processing principles underlying self-replication, the potential long term applications of programmable self-replicating machines, and the possibility of gaining insight into biological replication and the origins of life. Here we briefly summarize the historical development of work on artificial self-replicating structures in cellular spaces, and then describe some recent advances in this area. Past research is viewed as taking three main directions: early complex universal computer-constructors modeled after Turing machines, qualitatively simpler self-replicating loops, and efforts to view self-replication as an emergent phenomenon. We discuss our own recent studies showing that self-replicating structures can emerge from non-replicating components and that genetic algorithms can be applied to automatically program simple but arbitrary structures to replicate. We also describe recent work in which self-replicating structures are successfully programmed to do useful problem solving as they replicate. We conclude by identifying some implications and important research directions for the future.