by Herbert A. Simon
Why hierarchical assembly is exponentially faster than flat assembly - told through Hora and Tempus, two watchmakers.
tags: complexity, evolution, hierarchy, systems
Let me introduce the topic of evolution with a parable. There once were two watchmakers, named Hora and Tempus, who manufactured very fine watches. Both of them were highly regarded, and the phones in their workshops rang frequently - new customers were constantly calling them. However, Hora prospered, while Tempus became poorer and poorer and finally lost his shop. What was the reason?
The watches the men made consisted of about 1,000 parts each. Tempus had so constructed his that if he had one partly assembled and had to put it down - to answer the phone, say - it immediately fell to pieces and had to be reassembled from the elements. The better the customers liked his watches, the more they phoned him, the more difficult it became for him to find enough uninterrupted time to finish a watch.
The watches that Hora made were no less complex than those of Tempus. But he had designed them so that he could put together subassemblies of about ten elements each. Ten of these subassemblies, again, could be put together into a larger subassembly; and a system of ten of the latter subassemblies constituted the whole watch. Hence, when Hora had to put down a partly assembled watch in order to answer the phone, he lost only a small part of his work, and he assembled his watches in only a fraction of the man-hours it took Tempus.
It is rather easy to make a quantitative analysis of the relative difficulty of the tasks of Tempus and Hora. Suppose the probability that an interruption will occur while a part is being added to an incomplete assembly is p. Then the probability that Tempus can complete a watch he has started without interruption is (1−p)^1000 - a very small number unless p is .001 or less. Each interruption will cost, on the average, the time to assemble 1/p parts (the expected number assembled before interruption). On the other hand, Hora has to complete one hundred eleven sub-assemblies of ten parts each. The probability that he will not be interrupted while completing any one of these is (1−p)^10, and each interruption will cost only about the time required to assemble five parts.
All 4 of Hora's groups assemble in parallel. Locked groups are immune - interruptions only scatter the remaining unlocked parts.
Now if p is about .01 - that is, there is one chance in a hundred that either watchmaker will be interrupted while adding any one part to an assembly - then a straightforward calculation shows that it will take Tempus, on the average, about four thousand times as long to assemble a watch as Hora.
We arrive at the estimate as follows:
Multiplying these three ratios: (1/111) × (100/5) × 20,000 ≈ 4,000.
What lessons can we draw from our parable for biological evolution? Let us interpret a partially completed subassembly of k elementary parts as the coexistence of k parts in a small volume - ignoring their relative orientations. The model assumes that parts are entering the volume at a constant rate, but that there is a constant probability, p, that the part will be dispersed before another is added, unless the assembly reaches a stable state. These assumptions are not particularly realistic. They undoubtedly underestimate the decrease in probability of achieving the assembly with increase in the size of the assembly. Hence the assumptions understate - probably by a large factor - the relative advantage of a hierarchic structure.
Although we cannot, therefore, take the numerical estimate seriously, the lesson for biological evolution is quite clear and direct. The time required for the evolution of a complex form from simple elements depends critically on the numbers and distribution of potential intermediate stable forms. In particular, if there exists a hierarchy of potential stable "subassemblies," with about the same span, s, at each level of the hierarchy, then the time required for a subassembly can be expected to be about the same at each level - that is, proportional to 1/(1−p)^s. The time required for the assembly of a system of n elements will be proportional to log_s(n), that is, to the number of levels in the system. One would say - with more illustrative than literal intent - that the time required for the evolution of multi-celled organisms from single-celled organisms might be of the same order of magnitude as the time required for the evolution of single-celled organisms from macromolecules. The same argument could be applied to the evolution of proteins from amino acids, of molecules from atoms, of atoms from elementary particles.
A whole host of objections to this oversimplified scheme will occur, I am sure, to every working biologist, chemist, and physicist. Before turning to matters I know more about, I shall mention three of these problems, leaving the rest to the attention of the specialists.
First, in spite of the overtones of the watchmaker parable, the theory assumes no teleological mechanism. The complex forms can arise from the simple ones by purely random processes. Direction is provided to the scheme by the stability of the complex forms, once these come into existence. But this is nothing more than survival of the fittest - i.e., of the stable.
Second, not all large systems appear hierarchical. For example, most polymers - e.g., nylon - are simply linear chains of large numbers of identical components, the monomers. However, for present purposes we can simply regard such a structure as a hierarchy with a span of one - the limiting case. For a chain of any length represents a state of relative equilibrium.
Third, the evolution of complex systems from simple elements implies nothing, one way or the other, about the change in entropy of the entire system. If the process absorbs free energy, the complex system will have a smaller entropy than the elements; if it releases free energy, the opposite will be true. The former alternative is the one that holds for most biological systems, and the net inflow of free energy has to be supplied from the sun or some other source if the second law of thermodynamics is not to be violated. For the evolutionary process we are describing, the equilibria of the intermediate states need have only local and not global stability, and they may be stable only in the steady state - that is, as long as there is an external source of free energy that may be drawn upon.
Because organisms are not energetically closed systems, there is no way to deduce the direction, much less the rate, of evolution from classical thermodynamic considerations. All estimates indicate that the amount of entropy involved in the formation of a one-celled biological organism is trivially small. The "improbability" of evolution has nothing to do with this quantity of entropy, which is produced by every bacterial cell every generation. The irrelevance of quantity of information, in this sense, to speed of evolution can also be seen from the fact that exactly as much information is required to "copy" a cell through the reproductive process as to produce the first cell through evolution.
The existence of stable intermediate forms exercises a powerful effect on the evolution of complex forms - one that may be likened to the dramatic effect of catalysts upon reaction rates and steady-state distribution of reaction products in open systems. In neither case does the entropy change provide us with a guide to system behavior.
Let us turn now to some phenomena that have no obvious connection with biological evolution: human problem-solving processes. Consider, for example, the task of discovering the proof for a difficult theorem. The process can be - and often has been - described as a search through a maze. Starting with the axioms and previously proved theorems, various transformations allowed by the rules of the mathematical systems are attempted, to obtain new expressions. These are modified in turn until, with persistence and good fortune, a sequence or path of transformations is discovered that leads to the goal. The process usually involves a great deal of trial and error. Various paths are tried; some are abandoned, others are pushed further. Before a solution is found, a great many paths of the maze may be explored. The more difficult and novel the problem, the greater is likely to be the amount of trial and error required to find a solution.
At the same time, the trial and error is not completely random or blind; it is, in fact, rather highly selective. The new expressions that are obtained by transforming given ones are examined to see whether they represent progress toward the goal. Indications of progress spur further search in the same direction; lack of progress signals the abandonment of a line of search. Problem solving requires selective trial and error.
A little reflection reveals that cues signaling progress play the same role in the problem-solving process that stable intermediate forms play in the biological evolutionary process. In fact, we can take over the watchmaker parable and apply it also to problem solving. In problem solving, a partial result that represents recognizable progress toward the goal plays the role of a stable subassembly.
Suppose that the task is to open a safe whose lock has ten dials, each with one hundred possible settings, numbered from 0 to 99. How long will it take to open the safe by a blind trial-and-error search for the correct setting? Since there are 100¹⁰ possible settings, we may expect to examine about one-half of these, on the average, before finding the correct one - that is, fifty billion billion settings. Suppose, however, that the safe is defective, so that a click can be heard when any one dial is turned to the correct setting. Now each dial can be adjusted independently, and does not need to be touched again while the others are being set. The total number of settings that has to be tried is only 10 × 50, or five hundred. The task of opening the safe has been altered, by the cues the clicks provide, from a practically impossible one to a trivial one.
A considerable amount has been learned in the past decades about the nature of the mazes that represent common human problem-solving tasks - proving theorems, solving puzzles, playing chess, making investments, balancing assembly lines, to mention a few. All that we have learned about these mazes points to the same conclusion: that human problem solving, from the most blundering to the most insightful, involves nothing more than varying mixtures of trial and error and selectivity. The selectivity derives from various rules of thumb, or heuristics, that suggest which paths should be tried first and which leads are promising. We do not need to postulate processes more sophisticated than those involved in organic evolution to explain how enormous problem mazes are cut down to quite reasonable size.
When we examine the sources from which the problem-solving system, or the evolving system, as the case may be, derives its selectivity, we discover that selectivity can always be equated with some kind of feedback of information from the environment.
Let us consider the case of problem solving first. There are two basic kinds of selectivity. One we have already noted: various paths are tried out, the consequences of following them are noted, and this information is used to guide further search. In the same way, in organic evolution, various complexes come into being, at least evanescently, and those that are stable provide new building blocks for further construction. It is this information about stable configurations, and not free energy or negentropy from the sun, that guides the process of evolution and provides the selectivity that is essential to account for its rapidity.
The second source of selectivity in problem solving is previous experience. We see this particularly clearly when the problem to be solved is similar to one that has been solved before. Then, by simply trying again the paths that led to the earlier solution, or their analogues, trial-and-error search is greatly reduced or altogether eliminated.
What corresponds to this latter kind of information in organic evolution? The closest analogue is reproduction. Once we reach the level of self-reproducing systems, a complex system, when it has once been achieved, can be multiplied indefinitely. Reproduction in fact allows the inheritance of acquired characteristics, but at the level of genetic material, of course; i.e., only characteristics acquired by the genes can be inherited.
We have not exhausted the categories of complex systems to which the watchmaker argument can reasonably be applied. Philip assembled his Macedonian empire and gave it to his son, to be later combined with the Persian subassembly and others into Alexander's greater system. On Alexander's death, his empire did not crumble to dust, but fragmented into some of the major subsystems that had composed it. The watchmaker argument implies that if one would be Alexander, one should be born into a world where large stable political systems already exist. Where this condition was not fulfilled, as on the Scythian and Indian frontiers, Alexander found empire building a slippery business. So too, T. E. Lawrence's organizing of the Arabian revolt against the Turks was limited by the character of his largest stable building blocks, the separate, suspicious desert tribes.
The profession of history places a greater value upon the validated particular fact than upon tendentious generalization. I shall not elaborate upon my fancy, therefore, but will leave it to historians to decide whether anything can be learned for the interpretation of history from an abstract theory of hierarchic complex systems.
We have shown thus far that complex systems will evolve from simple systems much more rapidly if there are stable intermediate forms than if there are not. The resulting complex forms in the former case will be hierarchic. We have only to turn the argument around to explain the observed predominance of hierarchies among the complex systems nature presents to us. Among possible complex forms, hierarchies are the ones that have the time to evolve.
The hypothesis that complexity will be hierarchic makes no distinction among very flat hierarchies, like crystals, and tissues, and polymers, and the intermediate forms. Indeed, in the complex systems we encounter in nature, examples of both forms are prominent. A more complete theory than the one we have developed here would presumably have something to say about the determinants of width of span in these systems.
✦ memory · ☽ night · ∞ loops · ❧ margins · ◆ proof
a personal library in perpetual arrangement · MMXXVI