VON NEUMANN DAY Biological inspiration in computer science 40 years from the death of John von Neumann Lausanne (Switzerland), July 25th, 1997 Organization Logic Systems Laboratory Swiss Federal Institute of Technology Prof. Daniel Mange Phone: (+41 21) 693 26 40, Fax: (+41 21) 693 37 05 Email: tempesti@di.epfl.ch Goal A one-day international conference, organized by the Logic Systems Laboratory of the Swiss Federal Institute of Technology in Lausanne (EPFL) on Friday July 25th, 1997, will remember John von Neumann's contributions to bio-inspired computer science. With the assistance of international specialists in the field, and notably of Dr. Christopher Langton of the Santa Fe Institute (US), we will try to determine the progress of John von Neumann's dream: what have we achieved in the field of self-reproducing computing machines? In consideration of the subject and of the nationality of the speakers, all the presentations will be in English. Description In 1997, we commemorate the 40th anniversary of the death of John von Neumann. Aside from his contributions to mathematics, John von Neumann is considered one of the founders of the fields of computer science and engineering, notably giving his name to the standard architecture of computers. In the last years of his life, starting at the end of the forties, his research was marked by a strong biological inspiration. His last major contribution, the conception of a self-reproducing cellular automaton, demonstrates an exceptional vision and daring. Vision, because he borrowed from biology the concept of genomic information before the discovery of the DNA's double-helix structure (which implies that, to reproduce, an organism requires a description of itself). Daring, because his automaton is capable of both universal construction and universal computation. But neither von Neumann himself nor his direct successors (Burks, Thatcher, Codd, etc.) were able to simulate the automaton in its entirety, and much less to physically implement it. In 1984, Dr. Christopher Langton introduced a new self-replicating cellular automaton, simple enough to be entirely simulated. The repercussions of this work were considerable, both for computer science in general (with the birth of the concept of "artificial life") and for the self-replication of artificial organisms in particular. The goal of this special day is to revisit von Neumann's and Langton's historical contributions, and to ascertain our progress in the self-replication of computing machines. Program 8:30 Registration 9:00 D. Mange, Lausanne Introduction 9:15 P. Marchal, Neuch?tel Von Neumann's Life and Contributions to Computer Science 9:45 B. McMullin, Dublin Von Neumann's Problem: The Evolutionary Growth of Complexity 10:15 Coffee break 10:45 C. Langton, Santa Fe From von Neumann's Automaton to Langton's Loop 11:15 G. Tempesti, Lausanne Self-replicating Multicellular Automata 11:45 Lunch 14:00 J. Zahnd and M. Sipper, Lausanne Self-reproducing Loop with Universal Computation 14:30 J. Signorini, Paris Simulating von Neumann's Automaton 15:00 U. Pesavento, Princeton An Implementation of von Neumann's Self-reproducing Machine 15:30 Coffee break 16:00 P. Nussbaum, Neuch?tel Industrial Development of Self-healing Field-Programmable Processor Arrays 16:30 J.-O. Haenni and J.-L. Beuchat, Lausanne Hardware Implementation of von Neumann's Automaton 17:00 Demonstrations Abstracts "Introduction" by Daniel Mange, Lausanne "Von Neumann's Life and Contributions to Computer Science" by Pierre Marchal, Neuch?tel John von Neumann (1903-1957), one of the greatest mathematicians of the 20th century, has also been a pioneer of Computer Science. As early as 1946, he belonged to the team that designed and built the very first computing machine, still used as model for today's computers. Before describing the various contributions of John von Neumann to science, the key periods of his life will be mentioned. Much emphasis will be put on the self-reproducing automata that he imagined in order to extract from the natural self-reproduction problem its logical form. At that time he was urged more by the unreliability of hardware components than by pure A-Life considerations. Generalizing this concept opened him the door of complexity management. Finally, at his death's door, he addressed in his last book the distinction between a computer and a human brain. He studied them extensively in order to extract concepts for powerful computing. With respect to his contribution and especially his approach, consisting in the attempt to find, in biology, efficient solutions for information technology, he may also be considered as a pioneer of bio-inspired systems for computing. "Von Neumann's Problem: The Evolutionary Growth of Complexity" by Barry McMullin, Dublin The realisation of artificial Darwinian evolution is one conceivable - indeed, more or less obvious - route toward the realisation of a growth of complexity in artificial systems. In this talk I will explore just some aspects of the problem of achieving Artificial Darwinism in this sense. In particular, I will reassess and re-interpret the seminal work of von Neumann on cellular automata - arguing that the evolutionary growth of complexity was, precisely, the problem he was working on. Indeed, he solved one major element of it. This is in contrast to the conventional interpretation of von Neumann's work, which sees him as working on the problem of "self-reproduction" per se; it turns out that the latter interpretation can be mistakenly construed as rendering von Neumann's work "trivial", and thereby obscures his genuine achievement. "From von Neumann's Automaton to Langton's Loop" by Chris Langton, Santa Fe Coming soon... "Self-replicating Multicellular Automata" by Gianluca Tempesti, Lausanne An examination of Von Neumann's universal computer from a biological point of view reveals an interesting analogy with a unicellular organism: the tape containing the description of the machine can be seen as the equivalent of the biological genome, while the cellular automaton elements can be viewed as molecules. Von Neumann's machine, in its traditional implementation, does not lend itself to a hardware realization. Such a realization, however, becomes possible through the introduction of a new architecture, a multicellular automaton, roughly derived from the structure of multicellular organisms and based on the following three biologically-inspired features: multicellular organization, cellular differentiation, and cellular division. The development of such an architecture is the main goal of the Embryonics project. "Self-reproducing Loop with Universal Computation" by Jacques Zahnd and Moshe Sipper, Lausanne Self-reproducing, cellular automata-based systems developed to date broadly fall under two categories; the first consists of machines which are capable of performing elaborate tasks, yet are too complex to simulate, while the second consists of extremely simple machines which can be entirely implemented, yet lack any additional functionality aside from self-reproduction. In this talk we present a self-reproducing system which is completely realizable, while capable of executing any desired program, thereby exhibiting universal computation. Our starting point is a simple self-reproducing loop structure onto which we ``attach'' an executable program (Turing machine) along with its data. The three parts of our system (loop, program, data) are all reproduced, after which the program is run on the given data. The system reported in this paper has been simulated in its entirety. Thus, we attain a viable, self-reproducing machine with programmable capabilities. "Simulating von Neumann's Automaton" by Jacqueline Signorini, Paris We discuss the simulation of von Neumann's cellular automaton on a cellular processor. We first define the 29 states and the transition rule of the automaton. We then describe the implementation of the rule using only 13 bits of ram per processing element to encode the state and the rule, each processing element corresponding to a cell. The transition rule is very complicated due to the possible combinations of states between one cell and her four neighbor cells, each one of them having one of the 29 states. Indeed, there are more than 20 millions of local rules that govern the automaton. We explain how the implementation of the transition rule designs the micro-machine of the von Neumann automaton. We finally present experimental results based upon the simulation of general-purpose components of the automaton: pulser, decoder, periodic pulser, recognizer, crossing channel. "An Implementation of von Neumann's Self-reproducing Machine" by Umberto Pesavento, Princeton Von Neumann's universal constructor is a machine capable of reading descriptions of arbitrary machines and to build the machines described in the same environment in which it is embedded. A self-reproducing machine can be obtained from a universal constructor by providing it with a description of the constructor itself and adding to it the capability of copying the description provided. Von Neumann prooved the existence of a self-reproducing machine by providing a detailed implementation of it in a cellular automaton. Von Neumann's original design turns out to be quite elaborate and too cumbersome to be easily simulated in a computer. However, it is possible to modify von Neumann's original design to obtain a much smaller universal constructor. This modified design can be easily simulated in a computer. "Industrial Development of Self-healing Field-Programmable Processor Arrays" by Pascal Nussbaum, Neuch?tel Von Neumann was thinking in terms of cellular automata when he described self-replication principles. Today, in the industry, the cellular structure is more and more common. This trend began with the well known FPGAs (Field Programmable Gate Arrays), where each cell capable of implementing a simple combinational and/or boolean function. Now a new trend is emerging, whereby each cell is capable of implementing an automaton. This approach has been explored by Daniel Mange at the EPFL (Microtree), and is now being exploited in a more industrial context at the CSEM, where we are developing single-chip arrays of very small 8-bit processors. These new circuits have been called "Field Programmable Processor Arrays" (FPPAs). "Hardware Implementation of von Neumann's Automaton" by Jacques-Olivier Haenni and Jean-Luc Beuchat, Lausanne The first hardware implementation of von Neumann's 29-state automaton consists of a box, called biodule, containing a printed circuit board which implements the behaviour of a cell of the complete automaton. The future state of a cell is calculated by a logic circuit implemented using an FPGA, while the current state of each cell is graphically shown on a dot-matrix display. These biodules can be put together to form a small cellular automaton. One cell of the array is then connected to an EPROM, which sends excitation signals in order to build some simple organs, such as pulsers or decoders. This system does not allow the realisation of the entire self-reproducing automaton, but only of some small organs. The applications of this implementation lie mainly in the pedagogical domain as a demonstration tool. Practical information Location: The conference will be held in the auditorium EL1 of the Electrical Engineering Departement of the Swiss Federal Institute of Technology (map). The registration, as well as the coffee breaks, will take place at the entrance of this auditorium. Lunch will be served in one of the restaurants of the institute. Access: The institute may be reached by car, via highway N1, exit University-EPFL, or by public transportation (map). In the latter case, from the Lausanne train station, take the metro Lausanne-Ouchy (LO) direction Flon. At Flon, take the metro Lausanne-Sud-Ouest (TSOL) to the EPFL stop. Further information concerning the access to the site of the conference, as well as a list of possible accomodations in the area is available (in French) on the web page of the (canceled) AFCET's International Computer Science Summer School. Organization: The von Neumann Day is hosted by the Logic Systems Laboratory of the Swiss Federal Institute of Technology in association with the AFCET, the French Association of Science and Technology of Information and Systems, and the SISR, the Swiss Society of Computer Scientists, Swiss-French Section. Registration:The registration fees include access to the conference, coffee breaks and lunch. The registration form must be mailed back or faxed before July 1st, 1997. Cancellation: No refunds will be possible unless a written request for cancellation is received prior to July 1st, 1997. All refunds are subject to a 20% processing fee. Further information: You can contact the organizers directly: Gianluca Tempesti Phone: (+41 21) 693 26 76, Fax: (+41 21) 693 37 05 Email: tempesti@di.epfl.ch The address of our laboratory is: Logic Systems Laboratory Swiss Federal Institute of Technology IN-Ecublens, CH-1015 Lausanne (Switzerland) Phone: (+41 21) 693 26 40, Fax: (+41 21) 693 37 05 Last updated: May 1997, by Alex Bänninger. In case of problems with this site, please contact www_adm@lslsun.epfl.ch Logic Systems Laboratory, http://lslwww.epfl.ch