Lifelike Self-Replicators

Introduction

The concept of a cellular automaton derives from John von Neumann’s studies of the logic of life. In these studies, von Neumann focused on self-replicating structures with universal computational capabilities. Given the appropriate initial conditions, a universal computer can perform any finite computation, reproducing even the most complex biological behaviors. It is well known that the ECAs described in (Wolfram, 2002) and the Game of Life (Gardner, 1970; Evans, 2003; Adachi et al., 2008) have universal computational capabilities. It has been shown, furthermore, that certain one-dimensional CAs can generate structures that are equivalent to the components of an idealized digital computer, and that, by connecting these components in different ways, it is possible to implement any kind of algorithm. In brief, these CAs are equivalent to the better known - and simpler - Turing machine and share its ability to perform universal computation (Smith 1971).

The basic idea underlying the design of CAs as models of biological systems is that, in some cases continuous models (e.g. models based on differential equations) are unable to provide an adequate representation of the process. One example is self-replication of discrete units such as cells. In the 1940s and early 1950s, this problem led von Neumann to pose a crucial question: what kind of logical organization is required for an automaton to self-replicate? When he talked about automata, he was referring to artificial systems that could reproduce like living organisms. The theoretical backdrop was Turing’s theory of computation and Gödel’s work on the foundations of mathematics. More specifically, he was interested in Gödel’s Theorem of Incompleteness, according to which “there exist arithmetical truths that, in principal, can never be proved”. One of the key elements in Gödel’s proof is the role of self-referential propositions such as “this sentence is false”. Gödel shows that this kind of proposition gives rise to contradictions. According to Schuster & Sigmund (1983), biological self-replication is a particularly good example of self-referentiality. A genetic instruction such as “make of copy of yourself” ought to do nothing more than produce a copy of itself (self-reference). This would imply an unlimited lengthening of the genome, but not the construction of an organism. How can we escape the dichotomy between self-reference and self-replication? In von Neumann’s initial thought experiment, in 1948, he does not imagine a fixed lattice; the components in the system are free. The model uses the genetic information available in the system in two distinct ways - as un-interpreted (syntactical) and interpreted (semantic) data. The automaton consist of two parts: a flexible structure, and a set of replication instructions that allows the replication of both parts - i.e. replication of the structure and replication of the genome that gives rise to the structure (Schuster & Sigmund, 1983). Burks, one of von Neumann’s students, noted that the first process describes the dynamics of the system and referred to it as a “kinematic” model. Ulam introduced the idea of cells, suggesting that the self-replicating system could consist of discrete spatial units, distributed across a lattice. Von Neumann’s first model, developed between 1952 and 1953, had 29 states. Kinematic processes were replaced by the exchange of information among neighboring cells. Von Neumann pointed out that once the universal copier was in place, the system could evolve machines of ever increasing complexity. However, what interested him was not the simulation of biological or energy processes (Aspray and Burks 87), but the logic allowing a self-replicating machine to evolve “increased complication”.