VON NEUMANN DAY
Biological inspiration in computer science
|9:00||D. Mange, Lausanne
|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:45||C. Langton, Santa Fe
From von Neumann's Automaton to Langton's Loop
|11:15||G. Tempesti, Lausanne
Self-replicating Multicellular Automata
|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
|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
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.
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.
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, 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.
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.
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.
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).
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.
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:
Phone: (+41 21) 693 26 76, Fax: (+41 21) 693 37 05
The address of our laboratory is: