The Universal Constructor

What is it?

• Similar concept to the Universal Turing Machine
  
  
• A machine embedded within a CA which, when fed a "tape" containing suitable instructions, can construct any other cell assembly (hence the term Universal Constructor)
  
  
  
• It follows from this that the Universal Constructor is also capable of Universal Computation
  
  
• Consists of 3 basics actions:
• Translating the tape
• Copying the tape
• A controller to switch between translating and copying
  
  
  
• It can be fed instructions to build itself, and is thus capable of self-replication
  
  
  

Problems?

• Von Neumann designed it to be able to withstand some mutations, and thus be evolvable, but there are some practical difficulties with this...
  
  
  
• It's huge! (29 states per cell, 1000s of cells!)
  
  
  
  

Implementation

• Von Neumann designed a Universal Constructor, but didn't implement it
  
  
• The first real implementation was completed very recently, by Pasavento and Nobili [see U. Pasavento, "An Implementation of von Neumann's Self-Reproducing Machine", Artificial Life 2: 337-354 (1995)]
  
  
  
• An online demo is available