Computational properties of self-reproducing growing automata

Living organisms perform much better than computers at solving complex, irregular computational tasks, like search and adaptation. Key features of living organisms, identified in the paper as a basis for their success in solving complex problems, are: self-reproduction of cells, flexible framework, and modification. These key features of living organisms are abstracted into a computational model, called growing automata. Growing automata are suited for extremely large computational problems, such as search problems. Growing automata are representatives of soft machines. Soft machines can change their physical structure as opposed to hard machines which have fixed structure. An example of a soft machine is a living organism, an example of a hard machine is an electronic computer. The computational properties of soft and hard machines are analyzed and compared. An analysis of growing automata demonstrates their advantages, as well as their limitations as compared to hard machines.