self-reproducing automaton a formal model of self-reproduction of a kind introduced by von Neumann. He worked with an intuitive robot model and then with a well-defined cellular automaton model. Imagine a class of robotic automata made of robot parts and operating in an environment of such parts. There are computer parts (switches, memory elements, wires), input-output parts (sensing elements, display elements), action parts (grasping and moving elements, joining and cutting elements), and straight bars (to maintain structure and to employ in a storage tape). There are also energy sources that enable the robots to operate and move around. These five categories of parts are sufficient for the construction of robots that can make objects of various kinds, including other robots.
These parts also clearly suffice for making a robot version of any finite automaton. Sensing and acting parts can then be added to this robot so that it can make an indefinitely expandable storage tape from straight bars. (A ‘blank tape’ consists of bars joined in sequence, and the robot stores information on this tape by attaching bars or not at the junctions.) If its finite automaton part can execute programs and is sufficiently powerful, such a robot is a universal computing robot (cf. a universal Turing machine).
A universal computing robot can be augmented to form a universal constructing robot – a robot that can construct any robot, given its description. Let r be any robot with an indefinitely expandable tape, let F(r) be the description of its finite part, and let T(r) be the information on its tape. Now take a universal computing robot and augment it with sensing and acting devices and with programs so that when F(r) followed by T(r) is written on its tape, this augmented universal computer performs as follows. First, it reads the description F(r), finds the needed parts, and constructs the finite part of r. Second, it makes a blank tape, attaches it to the finite part of r, and then copies the information T(r) from its own tape onto the new tape. This augmentation of a universal computing robot is a universal constructor. For when it starts with the information F(r),T(r) written on its tape, it will construct a copy of r with T(r) on its tape. Robot self-reproduction results from applying the universal constructor to itself. Modify the universal constructor slightly so that when only a description F(r) is written on its tape, it constructs the finite part of r and then attaches a tape with F(r) written on it. Call this version of the universal constructor Cu. Now place Cu’s description F(Cu) on its own tape and start it up. Cu first reads this description and constructs a copy of the finite part of itself in an empty region of the cellular space. Then it adds a blank tape to the new construction and copies F(Cu) onto it. Hence Cu with F(Cu) on its tape has produced another copy of Cu with F(Cu) on its tape. This is automaton self-reproduction. This robot model of self-reproduction is very general. To develop the logic of self-reproduction further, von Neumann first extended the concept of a finite automaton to that of an infinite cellular automaton consisting of an array or ‘space’ of cells, each cell containing the same finite automaton. He chose an infinite checkerboard array for modeling self-reproduction, and he specified a particular twenty-nine-state automaton for each square (cell). Each automaton is connected directly to its four contiguous neighbors, and communication between neighbors takes one or two time-steps. The twenty-nine states of a cell fall into three categories. There is a blank state to represent the passivity of an empty area. There are twelve states for switching, storage, and communication, from which any finite automaton can be constructed in a sufficiently large region of cells. And there are sixteen states for simulating the activities of construction and destruction. Von Neumann chose these twenty-nine states in such a way that an area of non-blank cells could compute and grow, i.e., activate a path of cells out to a blank region and convert the cells of that region into a cellular automaton. A specific cellular automaton is embedded in this space by the selection of the initial states of a finite area of cells, all other cells being left blank. A universal computer consists of a sufficiently powerful finite automaton with a tape. The tape is an indefinitely long row of cells in which bits are represented by two different cell states. The finite automaton accesses these cells by means of a construction arm that it extends back and forth in rows of cells contiguous to the tape. When activated, this finite automaton will execute programs stored on its tape.
A universal constructor results from augmenting the universal computer (cf. the robot model). Another construction arm is added, together with a finite automaton controller to operate it. The controller sends signals into the arm to extend it out to a blank region of the cellular space, to move around that region, and to change the states of cells in that region. After the universal constructor has converted the region into a cellular automaton, it directs the construction arm to activate the new automaton and then withdraw from it. Cellular automaton selfreproduction results from applying the universal constructor to itself, as in the robot model.
Cellular automata are now studied extensively by humans working interactively with computers as abstract models of both physical and organic systems. (See Arthur W. Burks, ‘Von Neumann’s Self-Reproducing Automata,’ in Papers of John von Neumann on Computers and Computer Theory, edited by William Aspray and Arthur Burks, 1987.) The study of artificial life is an outgrowth of computer simulations of cellular automata and related automata. Cellular automata organizations are sometimes used in highly parallel computers.
See also ARTIFICIAL INTELLIGENCE , ARTIFI- CIAL LIFE , COMPUTER THEORY , TURING MACHIN. A.W.B.