Self Reproducing Computer Programs

Complexity: A Guided Tour

What Is Life? How did life originate, and what exactly constitutes being alive? While the origin of life is still hotly debated, the question of defining life itself is equally contentious. There is no consensus among scientists or the public.

Questions like “When does life begin?” or “What form could life take on other planets?” spark vigorous debate. The idea of creating artificial life is ancient, from legends of the Golem and Pygmalion to Frankenstein’s monster and modern movies like Blade Runner and The Matrix, and computer games like Sim Life. These narratives blend computation with life and evolution, raising the question: Can computers or robots be considered alive?

Defining Life Mechanistically: Many argue that computers can't exhibit life-like qualities due to several reasons:

• Autonomy: Computers only execute human-programmed instructions.

• Metabolism: Computers rely on external energy sources.

• Self-reproduction: Computers can't reproduce themselves without leading to an infinite regress.

• Survival instinct: Computers lack self-preservation or a drive for success.

• Evolution and adaptation: Computers can only change as pre-programmed.

Despite these arguments, the field of artificial life claims to have disproven them, particularly in self-reproduction and evolution.

Self-Reproduction in Computers: The self-reproduction argument posits an infinite regress problem: writing a computer program that prints an exact copy of itself seems impossible. Let's explore this with a simple program:

program copy
print("program copy")
print(" print(\\\\"program copy\\\\")")
print(" print(\\\\" print(\\\\\\\\\\\\"program copy\\\\\\\\\\\\")\\\\")")

Each line attempts to print the previous one, leading to an infinite loop. To avoid this, we must use the same information in two ways, as John von Neumann demonstrated with his self-reproducing automaton, a design principle used in biological systems.

A Self-Copying Program: Consider a simplified programming language and memory model. A program in this language can print an exact copy of itself using a loop and a variable to keep track of the current line.

program selfcopy
L = ip - 1
loop until line[L] = "end"
{
  print(line[L])
  L = L + 1
}
print("end")

This program uses a variable L to iterate over each line of code, printing them until it reaches the end. This dual use of information—both as data and instructions—avoids infinite regress.

The Deeper Meaning: This principle echoes Gödel's paradox and Turing's undecidability, where information serves dual roles, exemplified by the self-referential nature of statements and programs.

Self-Replication in DNA: DNA replicates similarly, using genes to encode the enzymes that copy DNA, with the DNA itself containing instructions for building these enzymes. Unlike the self-copying program, DNA also encodes its own interpreter, the cellular machinery for protein synthesis.

Von Neumann’s Self-Reproducing Automaton: Von Neumann's automaton, a mathematical design for a self-reproducing machine, included both the self-copying program and its interpreter, paralleling biological self-reproduction. His work laid the groundwork for the science of artificial life.

Von Neumann's Legacy: John von Neumann, a Hungarian-born genius, made groundbreaking contributions across multiple fields: mathematics, physics, computer science, economics, biology, and neuroscience. His achievements include foundational work in quantum mechanics, game theory, and the design of early electronic computers.

Von Neumann's exploration of self-reproducing automata and the links between computation and biology was ahead of its time. His vision of a unified theory of information processing across natural and artificial systems continues to influence the study of complex systems today.

Von Neumann's insights into self-reproducing automata and their implications for artificial life remain profound. His interdisciplinary approach and contributions continue to inspire research at the intersection of biology, computation, and complex systems.

After confirming that a machine could reproduce itself, von Neumann aimed to have computers (or programs) reproduce with mutations and compete for resources. This would counter arguments against computers having survival instincts and evolutionary capabilities. However, von Neumann died before addressing this evolution problem.

Researchers continued his work in the 1960s, leading to the field of evolutionary computation. John Holland, a significant figure in this field, was inspired by von Neumann through his Ph.D. advisor, Arthur Burks, who assisted von Neumann and continued his work.

Holland's interest in Darwinian evolution led him to create genetic algorithms (GAs), which simulate the evolution process in computers. His 1975 book "Adaptation in Natural and Artificial Systems" laid the foundation for GAs. Holland's approach involved "breeding" computer programs, similar to animal or plant breeding, to evolve better solutions to problems.

In GAs, a population of candidate solutions evolves over generations to solve a given problem. The process involves creating an initial population, calculating the fitness of each individual, selecting the fittest individuals to reproduce, and introducing mutations to create new generations.

GAs have been applied in various fields, including engineering, finance, and art. They have been used for aircraft design, satellite image analysis, chip design, financial forecasting, and more.

An example of a GA in action is the evolution of a control strategy for Robby, a robot designed to pick up soda cans. By evolving strategies over generations, the GA discovered efficient behaviors for Robby, outperforming a human-designed strategy.

GAs often find solutions that are unintuitive to humans, demonstrating their ability to explore and optimize complex design spaces. This capability has led to significant advancements in various fields, showcasing the power of evolutionary computation.

References:

Complexity: A Guided Tour - Melanie Mitchell