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). * 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.
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.
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). 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).
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.
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".
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".
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.
(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).
A New Self-Reproducing Automaton Based on a Multi-Cellular Organization
P. Marchal and C. Piguet are with the Centre suisse d'électronique
et de microtechnique SA, CH 2007 Neuchâtel (Switzerland).
Abstract
Introduction
Von Neumann's self-reproducing cellular automaton
Langton's self-reproducing loop
The multi-cellular automaton: a new self-reproducing automaton
based on a multi-cellular organization
1st property: constructional universality
2nd property: universal self-reproduction
3rd property: self-repair
Molecular vs. multi-cellular automata
Conclusion
References and Notes
Last updated in december 1997 by Alex Bänninger
In case of any problems with that site, please contact adm@lslsun.epfl.ch
Logic Systems Laboratory of EPFL
http://lslwww.epfl.ch