Recent research for space exploration, such as [2], [10], and [11] considers creating robot colonies on extraterrestrial objects for mining and manufacturing. However, sending such colonies through space is expensive [15], and one way to reduce the cost is to transport only one colony capable of self-replication.
The study of self-replicating systems was initiated by John von Neumann, who discussed cellular automata capable of building other cellular automata in [12]. The foundations of the automata theory were discussed by Claude Shannon in [14]. The theory of self-replicating systems proved to be a fruitful ground for research for many years. A detailed review of this field with many additional references is contained in [13], [9], and [3]. Pierre Kabamba introduced generation theory in [6] to analyze self-replicating systems.
In this paper, which originates from [4], I develop a new, much simpler, version of generation theory, which still captures all the details necessary for studying self-replication.
Once a robot colony which is capable of self-replicating is designed, a further effort must be made to identify its optimal seeds. A seed is a subset of the colony capable of manufacturing the whole colony. The optimization parameters might include the number of robots, the mass of robots, the cost of building robots on an extraterrestrial planet versus shipping them there, the time needed to manufacture robots at the destination, etc. Menezes and Kabamba gave a background and several algorithms for determining optimal seeds for some special cases of such colonies in [7], [8], and [9]. They also gave a lengthy discussion of the merits of the problem and an extensive reference list in [9].
In this paper, the new version of the generation theory, developed by the author, is used to arrive at a remarkably simple new solution to the optimal seeding problem.
In the framework of generation theory, the entities that can potentially reproduce are called machines, regardless of their physical nature (e.g., robots, microbes, or
lines of computer code). Reproduction is achieved by the action of machines on available resources, producing an outcome that may or may not be a machine itself. Menezes and Kabamba in [9] define a generation system as a quadruple
where
(4) 
is a generation function that maps a machine and a resource ordered list into an element in the universal set.
In this paper I introduce the following alternative definition of a generation system.
Note that an outcome of generation might not be a machine, however, I am interested only in outcomes which are machines, so I do not need to introduce the set U. If the outcome of generation is not a machine, I can define it to be the empty set.
Hence, I define a generation system to be a triple
I do not require a resource to be an ordered list. Menezes and Kabamba needed resources to be ordered lists in order to run their algorithms in [9].
I consider a more general generation function, which maps a subset of the set of machines and a subset of the set of resources into an outcome. I consider only outcomes which are subsets of the set of machines. An outcome might be the empty set.
This generalization of generation function is motivated by the observation that several robots might work simultaneously in order to produce a new robot, and a family of robots, working together, might produce more than one robot. Hence I define a generation function to be a function of the following form:
where 2
denotes the set of all subsets of the set S.
I allow cannibalization, i.e. certain machines after fulfilling their function can be taken apart for parts or materials, so they become resources. Hence it is possible that 
. However, I do not allow the empty generation situation when a resource becomes a machine without any transformation. Hence if a machine 
is generated by a set of machines 
acting on a set of resources 
, I require that 
. Menezes and Kabamba in [9] call such generation systems weakly regular.
A set of machines 
is called self-replicating if there exists a set of resources 
such that 
.
The general problem of seeding of a space colony can be put in the following simple form, where it becomes a transportation problem.
A set M of machines must be delivered to a certain destination. I assume that the set M is self-replicating. The set M exists at the base, so one solution of the problem is to load M at the base on some carrier and to transport it to the destination. However, transportation is expensive, and my budget is limited, so I must transport as little as possible. Note that for a mining colony, all of the resources R for self-replicating of M must be available at the destination except, possibly, for some machines in M which become resources after fulfilling their tasks. For all practical purposes I can assume that both sets M and R are finite. I assume that for any subsets 
and 
the generation function 
is given. I need the generation function 
) to be defined for all subsets 
and 
in order to run the algorithm described in the next section of the paper. In addition, I assume that a cost function 
)), which is vector-valued is given. The first component of 
)) provides the cost of running the generation function on the set (
), the remaining components of the function 
)) might be monetary cost of the manufacturing process, time required for the process, the energy consumption, etc. I also assume that for any subset 
a cost function 
), which also might be vector-valued, is given. The first component of 
) provides the cost of transporting all the machines in 
to the destination. I want to find all seeds of M, i.e. subsets of M capable of generating M. Seeds exist, because I assumed that M is self-replicating, so M is a seed of itself. In general, M might be the only seed of itself, however, I hope to find a number of different seeds. Moreover, I want to find a seed optimal with respect to T (G) and to U (or to a some subset of components of T (G) and U), and transport it to the destination. If there are several optimal seeds, I can choose the optimal seed randomly out of a set of several candidates.
I assume that the sets M and R are finite.
I construct the following directed labeled graph Γ.
The set of vertices of Γ is 2
. Two vertices 
and 
are connected by a directed edge if there exists a set of resources 
such that 
) and 
. Note that there might exist several distinct sets 
, satisfying the above description. However as the set R is finite, there might be only finitely many such 
. Denote these sets by 
. Hence any pair of vertices 
and 
in Γ might be connected by finitely many directed edges. An edge of Γ connecting vertex 
to 
is labeled by the function 
)).
As Γ is a directed graph, a directed path p in Γ is a finite sequence of directed edges 
such that the terminal vertex of any edge 
(except for the last one) coincides with the initial vertex of the next edge 
. For any vertex 
in Γ, I define its strongly connected component Γ
to be the set of vertices in Γ which can be connected to 
by a directed path. By construction, Γ
is the set of all seeds of the set 
. In particularly, the strongly connected component of the vertex M is the set of all seeds of M.
In order to find a seed of M with minimal transportation cost, I consider the set of all simple (without self-intersections) directed paths, (using any standard algorithm for the purpose [1]), connecting a vertex in Γ
to M. For any such path
let 
be the initial vertex of the edge 
and let 
)) be the label of the edge 
. Let 
)) be the first component of the function 
)), which provides the cost of runing the generation function 
), and let 
) be the first component of the function 
), which provides the cost of transporting all the machines in 
to the destination, (note that 
is the initial vertex of the path P).
The cumulative cost function for the path P is given by the following sum
As the set Γ
is finite, I can create a list of vertices of Γ
sorted by the value of the function Cost(P) and determine the seeds with minimal transportation cost.
This paper describes a novel approach to the problem of identifying an optimal seed of a self- reproducing automaton. This approach is based on generation theory, a mathematical construct capable of describing arbitrary matter and information processing systems in sufficient detail for studying the capacity of such systems for self-reproduction. This paper introduces a much simpler version of generation theory that still captures all the details necessary for studying self- reproduction. This new theory is used to arrive at a remarkably simple solution to the optimal seeding problem.
The main contribution of this paper is the novel abstraction it introduces, namely the simplified version of the generation theory. This contribution is significant. The provided solution to the optimal seed problem reinforces the significance of the result and illustrates its practical use.
The new solution to the optimal seeding problem, introduced in this paper, demonstrates that the new definition of the generating system, given in this paper, is a powerful mathematical tool. In a forthcoming paper [5], I shall describe the mathematical parallels between the new version of generation theory and certain well-studied objects of classical mathematics.
I want to thank Pierre Kabamba for introducing me to the initial version of the generation theory and Galip Ulsoy for helpful discussions.
[1] A. V. Aho, J. E. Hopcraft, and J. D. Ullman, The Design and the Analysis of Computer Algorithms, Reading, MA: Addison-Wesley, 1974.
[2] B. Foing, Roadmap for Robotic and Human Exploration of the Moon and Beyond, Proceedings of the 56th International Astronautical Congress, 2005, IAC-05-A5.1.01.
[3] R. A. Freitas, Jr. and R. C. Merkle, Kinematic Self-Replicating Machines, 2004, Georgetown TX: Landes Bioscience.
[4] R. Gitik, Generation Theory: Applications to Self-Reproducing Systems and Mathematical Insights, University of Michigan Control Group Report, 2006, CGR-06-14.
[5] R. Gitik, Mathematical Insights Provided by Generation Theory, in preparation.
[6] P. T. Kabamba, P. D. Owens, and A. G. Ulsoy, The von Neumann Threshold of SelfReproducing Systems: Theory and Applications, Robotica, 2011, 29, Special Issue 01, pp. 123-135.
[7] A. Menezes and P. Kabamba, A Combined Seed-Identification and Generation Analysis Algorithm for Self-Reproducing Systems, Proceedings of the 2007 American Control Conference, pp. 2582-2587.
[8] A. Menezes and P. Kabamba, An Optimal-Seed Identification Algorithm for Self-Reproducing Systems, Proceedings of the 58th International Astronautical Congress, 2007, IAC-07-D3.2.02.
[9] A. Menezes and P. Kabamba, Optimal Seeding of Self-Reproducing Systems, Artificial Life, 18, 2012, pp. 27-51.
[10] P. Metzger, Space Development and Space Science Together, an Historic Opportunity, Space Policy, 37, August 2016, pp. 77–91.
[11] P. Metzger, A. Muscatello, R. Mueller, and J. Mantovani, Affordable, Rapid Bootstrapping of the Space Industry and Solar System Civilization, J. Aerospace Engineering, 26, January 2013, pp. 18–29.
[12] J. von Neumann, Theory of Self-Reproducing Automata, Edited and completed by Arthur Burks, University of Illinois Press, 1966.
[13] P. D. Owens and A. G. Ulsoy, Self-replicating machines: Preventing Degeneracy, University of Michigan Control Group Report, 2006, CGR-06-02.
[14] C. Shannon, A mathematical Theory of Computation, Bell System Technical Journal, 27, 379-423 and 623-256, October 1948.
[15] J. R. Wertz and W. J. Larson (Eds.), Space Mission Analysis and Design, 3rd ed., 1999, El Segundo, CA: Microcosm Press.
Department of Mathematics, University of Michigan, Ann Arbor, MI, 48109 Email address: ritagtk@umich.edu