A New Self-Reproducing Automaton Based on a Multi-Cellular Organization

CAUTION : HTML uncomplete version, figures are missing

Daniel Mange*, Serge Durand, Eduardo Sanchez, André Stauffer, Gianluca Tempesti, Pierre Marchal, Christian Piguet

D.Mange, S.Durand, E.Sanchez, A.Stauffer, G.Tempesti are with the Logic Systems Laboratory, Department of Computer Science, Swiss Federal Institute of Technology, CH 1015 Lausanne (Switzerland).

P. Marchal and C. Piguet are with the Centre suisse d'électronique et de microtechnique SA, CH 2007 Neuchâtel (Switzerland).

* to whom correspondence should be addressed.


The possibility of achieving self-reproduction in a universal computing machine has been demonstrated by von Neumann in the 60's. Unfortunately, notwithstanding the improvements and the simplifications to which it has been subjected, it has not yet been possible to simulate, and much less physically implement, von Neumann's automaton in its entirety. The aim of this paper is to show that a new automaton, endowed with the same properties, can be simulated and physically implemented in its entirety. This result makes it possible to realize high-complexity integrated circuits (wafer-scale integration) capable, like living beings, of repairing themselves both locally (self-repair) and globally (self-reproduction) without external interventions. After demonstrating that van Neumann's automaton is a uni-cellular organism, i.e. containing a single copy of the genome, we will introduce the new automaton, based on a multi-cellular architecture. This architecture is comprised of a number of elements, each one simulating a living cell and containing a copy of the genome. Finally, we realized a physical implementation of our automaton which is, to the best of our knowledge, the first real automaton endowed of the properties of self-reproduction and universal computation.


In an article which recently appeared in this journal (1), Reggia et al. recalled the two main stages in the development of self-reproducing automata: (a) Von Neumann and his successors (Burks, Thatcher, Lee, Codd, Banks, etc.) developed universal computing automata, that is, self-reproducing automata capable of simulating a universal Turing machine. Unfortunately, the complexity of these automata is such that no physical implementation has yet been possible, and only partial simulations have been realized; (b) Langton and his successors (Byl, Reggia et al.) developed self-reproducing automata which are much simpler and which have been simulated in their entirety. These machines, however, lack any computing ability and are capable exclusively of self-reproduction. The purpose of this article is to propose a third approach, called "embryonics" (2). Borrowing three principles of organization (multi-cellular organization, cellular differentiation, and cellular division) from living organisms, we introduce the architecture of a new cellular automaton, complex enough for universal computation, but simple enough for a physical implementation through the use of commercially available digital integrated circuits. The method of construction, of self-reproduction and of self-repair of an artificial organism will be illustrated through a simple example, an up-down counter, and will lead to a realistic physical implementation. We will conclude by suggesting to interested biologists to analyze a first specimen of an artificial genome.

Our research aims at reaching two main objectives: (a) a technical objective, i.e. the conception and implementation of high-complexity integrated circuits ("wafer scale integration") endowed of quasi-biological properties (self-repair, self-reproduction); (b) a scientific objective, i.e. the establishment of the logical conditions which must be satisfied by a cellular automaton endowed of self-reproduction and universal computation capability.

Von Neumann's self-reproducing cellular automaton

The early history of the theory of self-reproducing machines is basically the history of John von Neumann's thinking on the matter (3). Von Neumann's cellular automaton (4), as well as all the machines described in this article, is based on the following general hypotheses: (a) the automaton deals exclusively with the flow of information; the physical material (usually a silicon substrate) and the energy (power supply) are given a priori; (b) the physical space is two-dimensional and as large as desired; (c) the physical space is "homogeneous", that is comprised by identical "elements" (5), all of which have the same internal architecture and the same connections with their neighbors; only the "state" of an element (the combination of the values in its memories) can distinguish it from its neighbors; (d) the reproduction is asexual: the daughter automaton is identical to the mother automaton.

The "element" of von Neumann's automaton is a finite state machine with 29 states; the future state of an element depends on the present state of the element itself and of its four cardinal neighbors (North, East, South, West). The exhaustive definition of the future state, the "transition table", thus contains 295 = 20,511,149 lines.

In his historic work (4), von Neumann successively showed that a possible

"configuration" (a set of elements in a given state) of his automaton can implement a "universal constructor" endowed with the three following properties: constructional universality (Fig. 1A), self-reproduction of the universal constructor (Fig. 1B) and self-reproduction of a universal calculator (Fig. 1C).

In biological terms, a "cell" can be defined as the smallest part of a living being which carries the complete plan of the being, that is the being's "genome". According to this definition, it can be stated that: (a) von Neumann's automaton is a uni-cellular organism: its genome is composed of the description of the universal constructor and computer D(Uconst + Ucomp) written in the memory M (Fig. 1C); as each element of this description needs 5 elements of the genome (4), it can be estimated that the genome is composed of approximately 5 times the number of elements of the universal constructor and computer. (b) The dimensions of von Neumann's automaton are substantial (in the order of 200,000 elements) (7). It has thus never been physically implemented and has been simulated only partially (8) (9). (c) The automaton implements the self-reproduction of a universal computer (a universal Turing machine).

If von Neumann and his successors Burks (4) (10), Thatcher (11), Lee (12), Codd (8), Banks (13), Nourai and Kashef (14) demonstrated the theoretical possibility of realizing self-reproducing automata with universal calculation, a practical implementation requires a sharply different approach. It was finally C. Langton, in 1984, who opened a second stage in this field of research.

Langton's self-reproducing loop

In order to construct a self-reproducing automaton simpler than this of von Neumann, Langton (15) adopted more liberal criteria. He dropped the condition that the self-reproducing unit must be capable of universal construction and computation. Langton's mechanism is based on an extremely simple configuration in Codd's automaton (8) called the periodic emitter, itself derived from the periodic pulser organ in von Neumann's automaton (4). The "element" of Langton's automaton is a finite state machine with only 8 states. The future state, as for von Neumann's, depends on the present state of the element itself and of its four cardinal neighbors; the exhaustive definition of the future state, the "transition table", is comprised of only 219 lines, a very small subset of the theoretically possible 85 = 262,144 lines.

Langton proposes a "configuration" in the form of a loop (Fig. 2), endowed notably of a constructing arm (pointing to the north in the left loop and to the east in the right loop) and of a replication program or "genome", which turns counterclockwise. After 151 clock periods, the left loop (the mother loop) produces a daughter loop, thus obtaining the "self-reproduction of Langton's loop".

Again referring to biological definitions (5), we can observe that: (a) Langton's self-reproducing loop is a uni-cellular organism. Its genome, defined in Fig. 2, requires 28 elements and is a subset of the complete loop which requires 94 elements. (b) The size of Langton's loop is perfectly reasonable, since it requires 94 elements, thus allowing complete simulation. (c) There is no universal construction nor calculation: the loop does nothing but reproduce itself. Comparing figures 1B and 2 reveals that the Langton's self-reproducing loop represents a special case of von Neumann's self-reproduction of a universal constructor. The loop is a non-universal constructor, capable of building, on the basis of its genome, a single type of machine: itself.

More recently, J. Byl (16) proposed a simplified version of Langton's automaton. Last, but not least, J. Reggia et al. (1) discovered that having a sheath surrounding the data paths of the genome (the "2" signals in Fig. 2) was not essential, and that its removal led to smaller self-reproducing structures which also have simpler transition functions. Moreover, they found that relaxing the strong symmetry requirement consistently led to transition functions that required fewer rules than the corresponding strong symmetry version. In the same vein, but with a completely different methodology, H.C. Morris (17) used the concept of "typogenetics", first introduced by Hofstadter (18), to reproduce strings of characters analogous to those of DNA in a one-dimensional environment. In all these constructions (Langton's, Byl's, Reggia's 2-dimensional and Morris' 1-dimensional), the initial configurations "do nothing but propagate" (17).

The multi-cellular automaton: a new self-reproducing automaton based on a multi-cellular organization

Our final objective is the realization of a computing machine offering at the same time the original properties of von Neumann's automaton (constructional universality, self-reproduction of a universal calculator) and the simplicity of Langton's loop (reasonable size, allowing not only a complete software simulation, but also a physical realization through existing digital integrated circuits). This objective can be achieved by introducing a new architecture, a "multi-cellular automaton", roughly derived from the structure of multi-cellular living beings, and based on the following three characteristics: (a) "multi-cellular organization". The proposed automaton meets all the general hypotheses described before in von Neumann's automaton. The "element" is essentially a random access memory (RAM) controlled by a small processor: a part of the state of this RAM, called the "gene", completely defines the permanent operation of the element. The value of the gene depends only on the position of the element in the whole automaton. In contrast to von Neumann's and Langton's states, the gene of an element is a stable state whose value does not usually change (19). Fig. 3A illustrates the example of a simple artificial organism , an "up-down counter", realized with nine elements, each element being defined by a gene. (b) "Cellular differentiation". Let us call "genome" the set of all the genes of an artificial organism, where each gene is characterized by its value and its position (its coordinates X,Y). Fig. 3A then shows the genome of the up-down counter. Let then each element of the automaton contain the entire genome (Fig. 3B): depending on its position in the whole, each element interprets the genome and extracts the gene which defines it. (c) "Cellular division". At startup, a single copy of the genome is contained in the mother element (Fig. 3C). The genome of the mother element is then copied into two neighboring daughter elements, and so on until the 2-dimensional space is completely programmed. As in the embryonic development of living multi-cellular beings, each mother element produces a maximum of two daughter elements (20).

1st property: constructional universality

Shannon (21) has shown that any n-variable logic function can be implemented with a finite number of multiplexers, each multiplexer realizing the universal one-variable logic function

f(z) = a0 * z' + a1* z (1)

where " ' " is the boolean NOT function, " *" is the AND function and " + " the OR function. The one-variable multiplexer (Fig. 4A) has a direct output f(z) which implements the combinational function (1) and a delayed output q(z) which implements the sequential operation by means of a D flip-flop; in addition, the presence of this flip-flop guarantees the possibility of realizing both the finite state machines and the shift registers needed by the implementation of any universal Turing machine. Fig. 4B shows a representation of the combinational function f(z) and the sequential function q(z).

As an example, let us consider the realization of the above-mentioned modulo-4 up-down counter, defined by the following sequences:

for M = 0: Q1,Q0 = 00 -> 01 -> 10 -> 11 -> 00 (counting up);

for M = 1: Q1,Q0 = 00 -> 11 -> 10 -> 01 -> 00 (counting down). (2)

A binary decision diagram (22) is a mode of representation of finite state machines based on the symbols of Fig. 4B. The up-down counter described by relations (2) can be represented by the binary decision diagrams of Fig. 4C. It is then evident that a multiplexer element, whose operation has been shown in Figs. 4A and 4B, can implement any one of the nodes of the diagrams of Fig. 4C, given programmable connections allowing: (a) short-range connections with the neighboring cells; (b) long-range connections with faraway cells. The final multiplexer element (without the genome memory) (23) (24) is shown in Fig. 4D. It is controlled by a 20-bit word GENE19:0, its "gene". The complete computation of the 9 genes of the up-down counter can be undertaken starting from the detailed characteristics of the multiplexer element described in (23) (24), and finally leads to the diagram of Fig. 3A which defines the entire genome of this counter.

As any combinational or sequential finite state machine, and therefore any Turing machine, can be represented under the form of several binary decision diagrams, it is always possible to implement such a machine by means of a finite number of multiplexer elements. We have thus demonstrated the "constructional universality" of our automaton.

2nd property: universal self-reproduction

In our automaton, self-reproduction is based on the presence of the complete genome in each element. To store the genome and to calculate the gene of each element as a function of the coordinates X and Y (cellular differentiation), we have chosen a straightforward implementation (Fig. 5A): (a) each element of the cellular automaton is equipped with a random access memory (RAM); each RAM contains the whole genome of the artificial being, i.e. the nine genes of Fig. 3A in the example of the up-down counter; (b) each RAM is addressed by a word (X,Y), where X is the horizontal coordinate and Y the vertical coordinate; (c) the calculation of the coordinates X and Y for each element is undertaken by a regular array of adders. It is easy to verify that each RAM gets the right coordinates at the right place, and therefore produces the right gene, each gene depending uniquely on these coordinates.

As the same pattern of coordinates produces the same pattern of genes, self-reproduction can be easily performed if the regular array of adders produces several occurrences of the basic pattern of coordinates (X = 1->2->3 and Y = 1->2->3 according to Fig. 5A); in our example, the repetition of the horizontal coordinates pattern, i.e. the production of the pattern X = 1->2->3->1->2->3 (Fig. 5B), produces one copy, the "daughter automaton", of the original or "mother automaton". Self-reproduction needs adders with a given modulo (in our example: modulo 3) and a number of spare elements; given a sufficiently large space, the self-reproduction process can be repeated for any number of specimens, both in the X and the Y axes. As in von Neumann's automaton, our automaton is essentially limited by the size of the memory (RAM) in which the genome is stored, located in each multiplexer element. For a given element, our automaton can thus implement and reproduce the class of Turing machines whose description (the genome) can fit in the available memory. In the frame of these limits, we can state that the proposed automaton performs "universal self-reproduction".

3rd property: self-repair

Every multicellular living organism is characterized by mechanisms of "self-repair" or "cicatrization": portions of varying importance of these organisms can be automatically reconstructed according to their original "blue-print", i.e. their genome. It can be shown that the proposed automaton is particularly well suited to self-repair. In the example of our up-down counter, assume that an element is faulty in any column (X = 2 in Fig. 6). Should such a fault be automatically detected using standard methods, such as BIST (built-in self-test) architectures (25), then, given sufficient space (a spare column with three elements to the extreme right of the original counter), the faulty cell is able to deactivate the column to which it belongs, to bypass the data coming from the left neighboring column and to obtain, by a global shift to the right of the horizontal coordinate X, a new, correct implementation of the original device. Our architecture, based on the presence of a genome in each element, leads to a straightforward "self-repair capability".

Molecular vs. multi-cellular automata

In biology, the "cell" is the smallest part of a living being containing the complete blueprint of the being, the "genome". On the basis of this definition, we have shown that von Neumann's automaton is a uni-cellular organism, since it contains a single copy of the genome (Figs. 1C and 7A). Each element of the automaton is thus a part of the cell, or, in biological terms, a "molecule". Von Neumann's automaton, therefore, is a "molecular automaton", and universal construction and self-reproduction are complex mechanisms, as they are caused by the interaction of thousands of elements, the molecules, each one realized by a finite state machine with 29 states. In contrast, the automaton we propose is a multi-cellular organism, as each of its elements contains a copy of the genome (nine copies in the case of the up-down counter of Fig. 7B). Each element of our automaton is thus a "cell" in the biological sense, and our automaton is truly a "multi-cellular automaton". The universal construction and self-reproduction are simple, even trivial, mechanisms, as the element (a multiplexer associated with the genome memory) has been conceived especially to carry out globally the operations of cellular differentiation and division.

The size of our automaton is extremely variable, depending essentially on the characteristics of the organism. Approximately, as many multiplexer elements are needed as there are nodes in the binary decision diagram(s) describing the organism to be implemented (see Fig. 4C). Both the simulation and the physical implementation of the element itself are easily realizable: using a programmable cellular network ("field-programmable gate array") and a RAM, we have implemented a prototype of the element, which we have called "biodule" (Fig. 8) (24). Using a number of these biodules, we have successfully implemented the self-reproduction and self-repair processes illustrated in Figs. 5B and 6.


We have proposed a new hardware implementation capable of the construction and self-reproduction of a universal computer (a universal Turing machine). This homogeneous architecture is also well suited to self-repair and seems to be a worthy candidate for the development of new very large scale integrated circuits (wafer scale integration).

As engineers, we have derived our inspiration from the rough organization of multi-cellular living beings to propose a realistic artificial object. We now want to offer to interested biologists the following considerations: (a) the contents of the random access memory, i.e. the genome, is finally written under the classical form of a sequential program, comprised of a series of instructions; (b)

In order to limit the number of connections, this program is copied from one element to another serially (bit by bit). The genome can thus be seen in the form of a linear succession of bits. (c) An arbitrary coding allows to represent each pair of bits 00, 01, 10, and 11 with the four letters, or "bases", of DNA A, C, G, T. (d) We thus obtain a sort of "artificial genome" in the form of a succession of bases A, C, G, T (Fig. 9A: example of the up-down counter). In this genome, we can identify (Fig. 9B) two "coordinate genes" ("X-coordinate gene" and "Y-coordinate gene"), which handle the computation of the coordinates X and Y; nine "functional genes" producing the nine genes of the example (Fig. 3A), which are the coding part of the genome; ten "switch genes" (26), used to express the functional genes according to the element's position in the organism (that is, according to the value of the element's coordinates); nine "configuration genes" which control particular functions in the element, for example its display.

The existence of these different categories of genes comes from purely logical needs deriving from the conception of our automaton. We would be glad to hear any eventual comments on the structure of our artificial genome from any biologist who might be interested in the matter.

References and Notes

(1) J. A. Reggia, S. L. Armentrout, H.-H. Chou, Y. Peng, Science 259, 1282 (1993).

(2) The term "embryonics" defines an electronic implementation based on a natural mechanism, embryology; this terminology originates from H. de Garis, in Proceedings Artificial Neural Nets and Genetic Algorithms, Innsbruck, April 1993, pp. 441-449.

(3) R. A. Freitas, W. P. Gilbreath, Eds, "Advanced Automation for Space Missions", NASA Conference Publication 2255 (1982).

(4) J. von Neumann, The Theory of Self-Reproducing Automata (Univ. of Illinois Press, Urbana, 1966).

(5) To avoid conflicts with biological definitions, we don't use the term "cell" to indicate the parts of a cellular automaton, opting rather for the term "element". In biological terms, a "cell" can be defined as the smallest part of a living being which carries the complete plan of the being, that is the being's "genome".

(6) A. Turing, in Proc. London Math. Soc. 42, 230 (1936); M. L. Minsky, Computation: Finite and Infinite Machines (Prentice-Hall, Englewood Cliffs, 1967).

(7) J. G. Kemeny, Scientific American, 58 (April 1955).

(8) E. Codd, Cellular Automata (Academic Press, New York, 1968).

(9) J. Signorini, in ACM and IEEE Proceedings of the Supercomputing '89 Conference, Reno, Nevada, 175 (1989); in Springer Proceedings in Physics 46, Berlin, 57 (1990); in Workshop on Cellular Automata, Espoo, Finland (April 17-18, 1991).

(10) A. W. Burks, Ed., Essays on Cellular Automata (Univ. of Illinois Press, Urbana, 1970).

(11) J. Thatcher, in Essays on Cellular Automata, A. Burks, Ed. (Univ. of Illinois Press, Urbana, 1970), chap. 5.

(12) C. Lee, in Applied Automata Theory, J. J. Tou, Ed. (Academic Press, London, 1968), pp. 217-234.

(13) E. R. Banks, in Eleventh Annual Symposium on Switching and Automata Theory, IEEE, 194 (1970).

(14) F. Nourai and R. S. Kashef, IEEE Transactions on Computers C-24, 766 (1975).

(15) C. G. Langton, Physica D 10, 135 (1984).

(16) J. Byl, Physica D 34, 295 (1989).

(17) H. C. Morris, in Artificial Life, C. G. Langton, Ed. (Addison-Wesley, Redwood City, 1989), pp. 369-395.

(18) D. Hofstadter, Godel, Escher, Bach (Basic Books, New York, 1979).

(19) Changes in the value of the gene occur both during growth (cellular division) and during self-repair; these changes characterize the transient operation of the element.

(20) The cellular division in question is that of somatic cells; the embryonic development of all living organisms can then be represented by a binary decision tree, with as many branches as there are cells in the organism. The classic example of Caenorhabditis elegans, with exactly 959 somatic cells, is described using such a tree in S. F. Gilbert, Developmental Biology (Sinauer Associates, Sunderland, Mass., ed. 3, 1991), pp. 264-269.

(21) C. E. Shannon, Bell System Technical Journal 28, 59 (1949).

(22) S. B. Akers, IEEE Transactions on Computers C-27, 509 (1978); R. E. Bryant, ACM Computing Surveys 24, 293 (1992); D. Mange, Microprogrammed Systems: an Introduction to Firmware Theory (Chapman & Hall, London, 1992).

(23) P. Marchal and A. Stauffer, in 2nd International ACM/SIGDA Workshop on Field-Programmable Gate Arrays, Berkeley, Calif., (1994).

(24) S. Durand, A. Stauffer, D. Mange, Technical Report, Biodule: an Introduction to Digital Biology (September 1994); this report is available from Logic Systems Laboratory, IN-Ecublens, CH 1015 Lausanne (Switzerland).

(25) E. J. McCluskey, Logic Design Principles with Emphasis on Testable Semicustom Circuits (Prentice-Hall, Englewood Cliffs, 1986); S. Durand and C. Piguet, in 2nd International ACM/SIGDA Workshop on Field-Programmable Gate Arrays, Berkeley, Calif., (1994).

(26) S. F. Gilbert, Developmental Biology (Sinauer Associates, Sunderland, Mass., ed. 3, 1991), p. 400.

(27) Supported by the Swiss National Science Foundation (grants No 21-36200.92 and No 20-39391.93).

Last updated in december 1997 by Alex Bänninger
In case of any problems with that site, please contact
Logic Systems Laboratory of EPFL