SIMPLE PROCEDURES OF SELF-REPRODUCING CELLULAR STRUCTURE REARRANGEMENT

摘要

A parallel substitution algorithm was the base for developing a simple procedure of constructing a self-reproducing cellular structure of arbitrary size. Von Neumann initiated investigation into self-reproducing structures about 40 years ago. A cellular automaton (CA) was and remains the main model for representing and studying logical self-replication models. Von Neumann's cellular automaton was a complicated machine. The second significant event in the history of investigating self-replication was a self-replication structure synthesized by Langton in 1984. The structure is much simpler than Von Neumann's automaton. It was a rectangular loop inserted in a 2D cellular-automaton space and based on a periodic emitter that was a fragment of Codd's cellular automaton and obtained in its turn by simplifying Von Neumann's automaton. A self-description (a genome) of a loop in the form of a sequence of automaton states circulated inside Langton's mother loop. Simultaneously with the construction of the daughter loop, the genome was replicated into it and then the loop generated its daughter. Langton's loop became a convenient and popular model of a self-reproducing structure for various kinds of investigation. It was simplified, i.e., loops in which the number of transition rules was less than in Langton's loop (it contained several hundreds of transition rules) were created. The loop was used as a model to test hypotheses referred to beginning of biological life (conditions of spontaneous emergence of replicators from random distribution of cell states in space, etc. were studied). The loop was endowed with properties of a constructor or ability for interaction with an external observer. A "useful replicator", i.e., a structure executing a computational program along with replication, was created based on the loop. Such a structure is a new paradigm of parallel fine-grain algorithms and architectures.