Self-Reproducing Automata

SELF-REPRODUCING AUTOMATA WALTER R. STAHL, M.D.* I. Introduction Automata theory is an advanced branch of modern mathematics that deals with the formalities ofcomputer programming and design ofrobots. The use of computers for such diverse activities as translating, writing music, controlling three-dimensional women's suit-knitting looms, and guiding missiles has demonstrated that automata theory—which may be considered the theoretical basis for computer technology—has a range of applicationfarwiderthan the more conventionaland older fields ofmathematics . This report deals with application ofautomata theory to a basic problem ofcellular biology, the logical control ofself-reproduction. The lateJohn von Neumann was the first to analyze self-reproduction as a formal problem ofautomata theory. He proposed two models which will be described in detail. Following this background discussion, a new type ofself-reproducing cell system, based on what I have called "string-processing automata " [i], is presented in detail. The model is fully operational on an SDS-920 computer and makes it possible to simulate basic cellular phenomena such as reproduction, differentiation, development oftumors (due to faulty self-reproduction control), virus take-over ofthe cell reproductive control system, mechanisms of antibiotics, and other matters. The cell model operates in a mathematically well-defined manner, byvirtue of the fact that elementary automata execute all operations in the cell system. The utility and importance of mechanical or formal simulations of biologicalentities areconsidered. A considerable parallelismexists betweenthe * Scientist, Oregon Regional Primate Research Center, Beaverton, Oregon, and Associate Professor , Department ofMathematics, Oregon State University, Corvallis, Oregon. This is publication No. 58 ofthe Oregon Regional Primate Research Center and was supported in part by National Institutes ofHealuYGrants FR 00163 and GM 11178-02. H. E. Goheen, L. B. Lusted, and R. W. Coffin provided valuable advice. 373 described model and the McCulloch-Pitts "logical neuron" [2], which is also highly simplified, but logically well defined, and thus susceptible to mathematical study. II. Some Concepts ofAutomata Theory Most published works in automata theory are very technical and therefore largely inaccessible to biologists at present. Fortunately, there are exceptions, such as von Neumann's own writings on automata theory, which are strikingly clear [3-6]· His emphasis was on content, not formalities. Non-professionals can certainly follow the fine review of automata theory by McNaughton [7] or the introductory volumes of Arbib [8] and Trakhtenbrot [9]. Among the more technical references one must cite Automata Studies by Shannon and McCarthy [10], which played an important role in developing contemporary automata theory, and books by Davis [11] and Gill [12]. An attempt will be made to provide a briefworking description ofautomata theory terms which are required to understand self-reproducing automata systems. An automatonis commonly defined as a "black boxwith states." It is an electronic or electro-mechanical device, with specified input and output channels, which operates in a deterministic manner, as by closing of relays , transistor pulse action, etc., to provide an output that is some logical function ofthe input. A telephone exchange is an automaton.When fed a series of pulses from the dialer, it uses switching circuits to connect him with the desired telephone line. Anycomputer can be considered an automaton , but one specialized (usually) for numerical processing. However, automata design can handle much more diverse logical problems, such as robot control, letter identification, etc. If the cell is "programmed by its genes," then it can be considered a natural or biological automaton. An automaton need not be rigidly "mechanical," in that it can involve random processes and be susceptible to mutation or errors. Examples of simulations possible with a cellular automaton have been given elsewhere [1, 13, 14]. In 1936 the British mathematician Alan M. Turing [15, 16] described a basic logical tool which is called the Turing Machine. This device is extremely simple in design and consists in nothing more than a reading head that travels about an indefinitely long tape which is divided into squares. The head is able to write or erase one symbol at a time in the 374 Walter R. Stahl · Self-reproducing Automata Perspectives in Biology and Medicine · Spring ¡965 squares and moves only one square at a time. With the tape and reading head is a Turing code...