The Cost of Combining the Results to Subproblems

Something to consider:  Recurrence relations must take into account the cost not only of solving subproblems but the combining the results.

One of the weaknesses in Elsberry and Shallit's essay is the short shrift they give to the arrangement of words within a sentence -- particularly in regard to the Weasel simulation.  In fact, it is so such a salient point that you wonder how anyone with a computer science background (namely Shallit) can be so blind to it.  E and S actually argue that, considering the random formation of separate words to a sentence as the solutions of the subproblems, the cost of getting them to link at precisely the right places into the correctly ordered sentences is trivial.  Of course, given their treatment of the problem mathematically, they are considering the spaces joining the words as no different from the characters in the words themselves.  Developing the "ks it" string is no different from developing the string "think", since the interrelationships between adjacent characters do not matter to the simulation at all.

If I have complete subassembly items of a jet plane, what is the information cost of  defining how they are put together -- or alternatively, what it is the computational cost of trial-and-error fitting together of components of the plane until it is assembled in a working fashion, in the absence of that information?

Even in "embarrassing parallel" problems, how much forethought or arranging needs to be put into how to put together the results of the distributed computation?   Considering natural selection as a computational problem, what is the cost of massively parallelizing?  Well, there is a definite cost to having too many mutations at one time.  This reduces the bandwidth and makes for an "embarrassing" amount of redundancy.  Now, a mutations themselves are distributed over a large population, and with a large population you can experiment here and there.   Mutational experiments can then combine without destabilizing the species.  However, this makes it very, very difficult for two mutations  needed to combine for a special result to combine in one special hybrid individual.  If the two mutations are not quite "neutral enough" they will likely never meet up.  Then, you say, small populations are often somewhat isolated.  Maybe it is this isolation, a "founder effect" and such that affords the complementary mutations a chance to find each other.  But then it is fortuitous for them both to occurred in the same small population.  Then, you say, it is some special combination of small populations occassionally.  This final retreat is rather like a shell game, I think.  In the end, if there is some ideal combination of ideal gene flow between ideally sized local populations, isn't this itself a deus machina?

But then, isn't that evolutionary science?  Speculating what remarkable conditions would be needed for natural selection to have done it, and then asserting then that this remarkable set of conditions is indeed what was the case, since we know that natural selection has brought it about?

This reminds me of the "fortuitous tree"...