News Archives

[Colloquium] Artificial Cells as Reified Quines

December 10, 2010

Watch Colloquium: 

M4V file (544 MB)
MOV file - Part 2 97 MB)
MOV file - Part 3 (90 MB)


  • Date: Friday, December 10, 2010 
  • Time: 12noon — 12:50 pm 
  • Place: Centennial Engineering Center, Room 1041

Lance R. Williams
Assoc. Professor Department of Computer Science University of New Mexico

Cellular automata (CA) were initially conceived as a formal model to study self-replication in artificial systems. Although self-replication in natural systems is characterized by exponential population increase until exhaustion of resources, after more than fifty years of research, no CA-based self-replicator has come close to exhibiting such rapid population growth. We believe this is due to an intrinsic limitation of CA’s, namely, the inability to model extended structures held together by bonds and capable of diffusion.

To address this shortcoming, we introduce a model of parallel distributed spatial computation which is highly expressive, infinitely scalable, and asynchronous. We then use this model to define a series of self-replicating machines. These machines assemble copies of themselves from components supplied by diffusion and increase in number exponentially until the supply of components is exhausted. Because they are both programmable constructors for a class of machines, and self-descriptions, we call these machines reified quines.

Bio: Lance R. Williams received his BS degree in computer science from the Pennsylvania State University and his MS and PhD degrees in computer science from the University of Massachusetts. Prior to joining UNM, he was a post-doctoral scientist at NEC Research Institute. His research interests include computer vision and graphics, digital image processing, and neural computation.