In Nanosystems, after proposing detailed designs for low-level molecular machinery components (gears, rods, and the like), K. Eric Drexler proposes two high-level designs for a self-reproducing molecular robot, an "assembler", in the tradition of self-replicating machines first proposed and computationally modelled by John von Neumann, and inspired by the ability of living things to reproduce themselves. Drexler argues along the lines that his designs can reproduce themselves in a short period of time based on the degrees of freedom of the robot arms, their high frequency of operation at the molecular scale, and some other general considerations.

Tim May has observed that it is one thing to count molecules and degrees of freedom/frequency of very generally and vaguely specified "operations", and quite another to design a machine that works correctly through every one of the (trillions of?) physical states needed to get from organic inputs to the complex gears, ratchets, bearings, and subassemblies to new assemblers. The problem is similar in structure to designing a metabolism that turns raw food into another bacterium, with the added complexity of mechanical in addition to chemical operations.

In the cases of bacterium we have thousands of distinct chemical reactions, still not fully mapped. Full metabolic mapping is much more difficult than full genome mapping. Even with this complexity a bacterium is still very sensitive to environmental conditions. No bacterium is truly self-replicating in the sense of being self-sufficient; instead it is highly dependent on the surrounding food web. The simplest self-sufficient replicator may be the lichen, but that has correspondingly slow replication time. Generality vs. speed is probably a fundamental tradeoff.

While going from macroscopic industrial parts proposed by von Neumann, or the nucleic acids, amino acids and myriad of tertiary biochemicals in bacteria, to atomic-scale diamondoid parts reduces the search space, and thus complexity, but this also reduces the degrees of design freedom. It could be that the search space of diamondoid replicators is so small that there is no possible configuration of, say, 10 million carbon atoms can copy itself in practice, when we get down to the details of atomic placement in each operation. A particularly difficult task in atomic placement for one small segement of a Stewart platform (eg assembling the ratchet complex) may necessitate a blowup in the complexity of the platform itself or in the machinery that brings molecules to and places them for the platform. To be truly self-replicating we need to close all the loops in the graph of operations. Attempts to close the last 1% ("vitamins") might introduce even more open loops than we close. The minimum complexity might easily exceed the degrees of freedom in the search space, in which case a solution does not exist.

On the other hand, we have no good theory about the minimal complexity needed for closing such an graph in terms of real operations. The graph itself is like that for an autocatalytic metabolism, or the graph of all industrial operations in our economy, but these also are too complex to model in sufficient detail with our current tools.

Some kinds of tech, like 3D printers and CAD-driven agile manufacturing, bring a more closed loop industrial economy at the cost of replication time or efficiency (just as with the lichen). I suspect the same economies occur in the atomic-scale, MHz region -- we will have very fast robots pumping out a certain class of products quickly, but not capable of self-replication. On the other hand, the the trillionth widget will not bring in very much revenue, so flexibility will become more of any economic driver as industry gets faster. With robot cycles to spare, we will likely sacrifice orders of magnitude in efficiency for the sake of flexibility.

We may also have tools on the horizon that allow us to design machines orders of magnitude more complex than a human engineer could design (or fully understand). Given sufficiently rapid and accurate simulation of those operations, a genetic algorithm, based on the abstract algorithm of Darwinian evolution (artificial or natural selection), can create "probably, approximately correct" operation graphs, for example finding many of the most closed configurations of a diamondoid assembler. Such a task would be computationally prohibitive for an exact deterministic algorithm, or a human engineering team. Given sufficiently accurate molecular simulation, GAs might also be useful for reconstructing metabolic pathways in living things from partial information (genetic code, roles in food web, etc.), currently intractable. GAs have already tackled some problems that are simple to specify but hard to solve, eg finding rules that identify transmembrane proteins based on amino acid sequence, protein folding, and the like.

One of the most compelling aspects of Drexler's diamondoid paradigm is that it makes the specification of such automated design tools a much simpler affair. This allows the vast bulk of the complexity to be tackled by computer. I strongly suspect some CAD tools along these lines will pan out, so that the major problem with the complexity of self-replication will not be our lack of design sophistication, but the possibility that a small diamondoid self-replicator may be impossible in that narrow design space.

Sometime during the pre-genetic phase of evolution, during the few hundred million years between the cooling of the earth and the birth of the first self-reproducing bacterium, life went through a kind of process whose nature is obscure, but from the astronomical search space of metabolisms found the highly complex nucleic/amino acid combination. One computational model of this process is the "autocatalytic set", in which a metabolism of of polymers (perhaps RNA or an interaction between RNA and a few amino acids) grows molecules from its current set. Either this process was much more computationally effective than intuition would tell us, or else there are many different ways for a biological system to stably reproduce, and it didn't take much pre-genetic evolution to find it. So while self-reproduction may be complex in terms of the minimal genetic code and metabolism needed to pull it off, there may in that astronomical search space a very large number of solutions that reproduce, so that the overall design difficulty, more precisely logical depth, of physical self-reproduction is not very high.

References:
Introduction to Algorithmic Information Theory a field relevant to determining the complexity of data structures
Ralph Merkle has many links to good papers on molecular nanotechnology
K. Eric Drexler, Nanosystems