Kinematic Self-Replicating Machines

© 2004 Robert A. Freitas Jr. and Ralph C. Merkle. All Rights Reserved.

Robert A. Freitas Jr., Ralph C. Merkle, Kinematic Self-Replicating Machines, Landes Bioscience, Georgetown, TX, 2004.


3.25.4 Toth-Fejel Kinematic Cellular Automata (2003-2004)

Building on his KCA concepts described in Section 3.8, Tihamer Toth-Fejel at General Dynamics Advanced Information Systems was awarded a Phase I NIAC contract to study “Modeling Kinematic Cellular Automata: An Approach to Self-Replication” during 1 October 2003 through 31 March 2004 [1299].

According to the abstract of the original proposal, the study will “design a useful Self-Replicating System (SRS). As shown by NASA’s summer study Advanced Automation for Space Missions [2] and other smaller studies, the development of dynamically reconfigurable SRSs that implement Universal Constructors can revolutionize future space missions. For example, a self-replicating lunar factory could build solar cells and other manufactured tools with which to explore and develop the Moon with exponential growth. But despite the fact that these studies showed the tremendous power of machine self-replication, there have been no serious attempts to further the field. However, two recent small efforts (Sections 3.18 and 3.23) have resulted in some success. We propose to build upon one of those successes by designing a system of Kinematic Cellular Automata (KCA) cells that are configured as a limited implementation of a Universal Constructor. The trivial self-replication is easy, but the final goal of autotrophic self-replication is certain to be extremely difficult. So there is a huge unexplored area between these two extremes, and we believe that an iterative approach of gradually moving complexity out of the environment and into the cell is the best chance at characterizing it.”

“[The work will] start by simulating a trivial self-replication process in a 3-D world that is as simple as possible – a KCA in a moving gantry/arm configuration placed in an environment full of inert cells (the zero-complexity scenario). After this testbed simulation confirms the KCA reconfiguration algorithms, the one-complexity scenario will start with each inert cell divided in half, and the gantry/arm KCA will assemble these subcomponents into complete KCAs before reconfiguring them into another KCA. After successfully developing the algorithms necessary, the dividing iteration will be repeated for the two-complexity scenario. The idea is to move the complexity out of the environment and into the cell, ultimately towards a system that requires only feedstock molecules, energy, and information to build copies of itself and any of a wide variety of other products. As a bonus, developing each successful scenario will result in both hardware designs of useful modular robots and the control algorithms that run them.”

According to the Final Report [1299], Toth-Fejel’s analysis showed that the complexity of a useful KCA replicator can be less than that of a Pentium IV microprocessor. For instance, the helical stacking of passive domino-shaped alternating bricks of metal and insulator material yields an astonishingly simple and robust design for an electromechanical solenoid actuator that would seem to require very little manufacturing sophistication to fabricate. The study also developed a reasonable hierarchy for a practical replicator system including a workable preliminary design that could be applied at macro, micro, and nano scales. In this view, a KCA replicating system is a hierarchy consisting of subsystems which are made up of Cells (Figure 3.79), which are made up of Facets, which are made up of Parts, which are made up of self-assembled Subparts – and at the bottom, everything is made of molecules. During replication the system assembles simple inert parts into symmetrical facets that form modular dynamic cells that are configured as Connector, Transporter, and Controller subsystems to make up a Self-Replicating System (SRS).

Toth-Fejel’s Transporter subsystem design consists of less than 12 cells, two of which grab parts, one at a time, and three on the bottom which actually move the subsystem around on a “base plane” of about 50 cells. The Connector subsystem serves to connect Parts – while each Transporter is composed of 12 cells that moves one part around, a Connector contains a Transporter for each part that it connects, plus one Transporter for each preparation tool. For the Controller subsystem, Configurable Logic Blocks (of which 120 are needed to implement the tiny 8-bit PicoBlaze processor) are employed that are functionally identical to those in existing implementations of Field Programmable Gate Arrays (FPGAs), thus allowing the use of commercially available VHDL (VLSI Hardware Description Language) interpreters that can automatically specify the necessary connections between the CLBs, and also allowing the use of other existing soft processor peripherals which means that the software for a large class of Utility Fog (Section 3.8) configurations already exists. The study focused much attention on achieving closure at a digital information level. For instance, a design for a simple op-amp consists of a mosaic of 50 Wang tiles of 11 different tile types, each tile a very simple and easily-manufactured cell having the functionality of, for example, a wire and transistor; a similarly designed NAND gate is an array of 42 Wang tiles of 8 different tile types (Figure 3.80 and caption). Dozens of specific control-sequence subroutines, listed in an Appendix A of the Final Report [1299], were written to simulate (and visualize) one complete assembly operation using a Transporter and Connector (Figure 3.81). Noted Toth-Fejel [1299]: “Only a small number of [these subroutines] needed to be implemented in MaxScript to simulate an assembly process. Surprisingly few subroutines were necessary to code this simulation. Hundreds of steps very similar to this assembly step would be necessary to build a single modular cell.”

One of the authors of this book (Freitas) served as a technical consultant for this study, along with Matt Moses as the second consultant.


Last updated on 1 August 2005