one classification of complexity measures

from page 5 of this document

Some interesting overview information in "Complexity Measures in Manufacturing Systems" by DeTony et al.  (Not sure how accurate some of the characterizations of the different complexity measures are.)

Evolutionary Informatics

Evolutionary informatics, a branch of information theory, studies the informational requirements of evolutionary processes. Its most significant result is a conservation principle. According to this principle, the information needed to find a successful search is never less than the information required to make the original search successful. Consequently, the higher-level search for a search is never easier than the original lower-level search. Conservation of information implies that information, like money or energy, is a commodity that obeys strict accounting principles. Accordingly, searches, in successfully locating targets, cannot expend more information than originally deposited. Conservation of information has far-reaching implications for evolutionary theory, pointing out that the success of evolutionary processes in exploring biological configuration space always depends on preexisting information. In particular, evolutionary processes cannot create the information required for their success from scratch.
  - William Dembski, "What Does Information Tell Us About ID?", Salvo 

Of Time and Miracles

Is crossing a large chasm of space and time resources a miracle?

Treating the empirical time scale of the evolution theoretically as infinity they have then an easy game, apparently to avoid the concept of purposesiveness. While they pretend to stay in this way completely ‘scientific’ and ‘rational’, they become actually very irrational, particularly because they use the word ‘chance’, not any longer combined with estimations of a mathematically defined probability, in its application to very rare single events more or less synonymous with the old word ‘miracle’.”
 -- Wolfgang Pauli to Niels Bohr, 2/15/1955, letter 2015 in von Meyenn (2001), p.105

Baez on Information Geometry

I think I've struck some gold here concerning information geometry in a series by John Carlos Baez.

Start with part 8 where Baez gets into the relationship to evolution.  Some reminder about thermodynamic models:

Physicists love to think about systems that take only a little information to describe. So when they get a system that takes a lot of information to describe, they use a trick called 'statistical mechanics', where you try to ignore most of this information and focus on a few especially important variables. For example, if you hand a physicist a box of gas, they'll try to avoid thinking about the state of each atom, and instead focus on a few macroscopic quantities like the volume and total energy. Ironically, the mathematical concept of information arose first here—although they didn't call it information back then; they called it 'entropy'. The entropy of a box of gas is precisely the amount of information you've decided to forget when you play this trick of focusing on the macroscopic variables. Amazingly, remembering just this—the sheer amount of information you've forgotten—can be extremely useful... at least for the systems physicists like best.

He goes on to say that in biology, there is a lot less information in the system that can be forgotten... This goes back somewhat to the use of "entropy" to correlate to different kinds of information.  The (average) loss of uncertainty/entropy in Shannon information, for example. He goes on to talk about alleles as rival hypotheses.

The analogy is mathematically precise, and fascinating. In rough terms, it says that the process of natural selection resembles the process of Bayesian inference. A population of organisms can be thought of as having various 'hypotheses' about how to survive—each hypothesis corresponding to a different allele. (Roughly, an allele is one of several alternative versions of a gene.) In each successive generation, the process of natural selection modifies the proportion of organisms having each hypothesis, according to Bayes' rule!

It appears that this approach looks at information in terms of a distance from a destination state of stability.  So in that sense, it is more about relative information.  

But what does all this have to do with information? . . .  first discovered by Ethan Atkin. Suppose evolution as described by the replicator equation brings the whole list of probabilities p_i  — let's call this list p —closer and closer to some stable equilibrium, say q.  Then if a couple of technical conditions hold, the entropy of q relative to p keeps decreasing, and approaches zero.   Remember what I told you about relative entropy. In Bayesian inference, the entropy q relative to p is how much information we gain if we start with p as our prior and then do an experiment that pushes us to the posterior q. So, in simple rough terms: as it approaches a stable equilibrium, the amount of information a species has left to learn keeps dropping, and goes to zero!  . . .  You can find [precise details] in Section 3.5, which is called "Kullback-Leibler Divergence is a Lyapunov function for the Replicator Dynamic". . . .  'Kullback-Leibler divergence' is just another term for relative entropy. 'Lyapunov function' means that it keeps dropping and goes to zero. And the 'replicator dynamic' is the replicator equation I described above.  . . .  [This approach] uses information geometry to make precise the sense in which evolution is a process of acquiring information. 

Baez offers some background to this in Gavin E. Crooks' Measuring thermodynamic length and in part 1 of his series.

But when we’ve got lots of observables, there’s something better than the variance of each one. There’s the covariance matrix of the whole lot of them! Each observable  fluctuates around its mean value … but these fluctuations are not independent! They’re correlated, and the covariance matrix says how.
All this is very visual, at least for me. If you imagine the fluctuations as forming a blurry patch near the point , this patch will be ellipsoidal in shape, at least when all our random fluctuations are Gaussian. And then the shape of this ellipsoid is precisely captured by the covariance matrix! In particular, the eigenvectors of the covariance matrix will point along the principal axes of this ellipsoid, and the eigenvalues will say how stretched out the ellipsoid is in each direction!

As I recall, the eigenvalues will be in bits of error in terms of the units of the parameters.

Adleman's K-potency and Kauffman's Atoms

One of the motivations for the sequence-space probability dispersion matrix is that as a model it might estimate the computational depth of nucleotide sequences, or the relative depth between two nucleotide sequences.   How deep is a given nucleotide sequence?

Kauffman writes in a recent foreword that the universe has produced every kind of atom it could produce (an ergodic process, whereas enumerating the realizable proteins is a non-ergodic process), but Leonard Adleman has elsewhere written in "The Rarest Things in the Universe" (among "entropy and information" here) that atoms with higher counts of protons than we've thus far encountered could be considered to have larger depth (and thus be somewhat analogous to Kauffman's sequences).

I am not a physicist, but I suppose it is possible to theorize about an atomic nucleus with a million protons. But what if I want to create one? It appears that producing transuranic elements takes huge amounts of time/energy and the greater the number of protons, the more time/energy it takes. It is even conceivable (to me at least) that there is not enough time/energy available (at least on earth) to actually produce one. Like the prime factorization of , it may exist in theory but not in reality. On the other hand, physicists from Russia and America, using lots of time/energy, have created an atomic nucleus with 118 protons called Ununoctium. Ununoctium is analogous to Childers’ prime factorization; both exist in reality; both were very costly to create.

In his 1979 paper "Time, Space, and Randomness," Adleman develops an idea about "K-potency" motivated by an analogy with thermodynamics, specifically chemical reactions that take much less time going in one direction than the other.

This approach to "one-way functions" is important to crytography, incidentally.  His definition for K-potency follows here:

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"...

islands of functionality and the flash of genius

Hazen et al illustrate some alternative ideas of functional protein accessibility in protein space, where the plane represents the dimensionality of protein space (2 is much, much fewer than what would be needed) and the E axis represents the catalytic usefulness of the various points in protein space (in essence, a fitness landscape):

D has more of a needle-in-a-haystack problem than A, B, or C, due to its relatively small hypervolume (area in the figure) of protein space.  But it's not the only aspect that makes in inaccessible.  The relative distance from other islands of functionality.  Using the above figure a little out of its intended representation, we see that B and C are relatively close together, so that not as vast a distance of neutral mutation would have to be crossed to get from B to C as from A to D.

But vast oceans of neutral mutation to be crossed are not the only impediment to finding the points of especially high functionality ... There is also the fact that less optimal peaks might serve as attractors that divert computational resources away from the brass ring.  In this case, the good is the enemy of the best.

D of Hazen et al's figure above corresponds to this diagram from one of Douglas Axe's papers, where sequence/protein space is represented by only one dimension:

Here the white noise of suboptimal adaptations might be considered negligible, all of the being more or less neutral in that they don't change the survivability rate of the organisms enough to inhibit the traversal of sequence space.  It is possible that the neutral is filled with many little hills and valleys, a so-called rugged landscape.  In the Picasso-esque landscape below, it may be that the difficulty in finding the high peak of innovation is compunded, both by the volume of sequence/protein space to search but also by the attractive "force" of suboptimal solutions.

The size of the relevant space to be searched along with the distractive force of more accessible (more "obvious") solutions might contribute to the Non-Obviousness of the more optimal solution.

It would seem that both of these have relevance to Bennett's concept of "logical depth", as they both may drive up the necessary computational resources (or, the amount of brute force "tinkering") to realize the non-obvious solution -- where a flash of genius might render all that brute force tinkering unnecessary.  

In Shadows of the Mind, in which Roger Penrose argues for mathematical insight requiring something beyond computation, Penrose has a section on "Things that computers do well -- or badly":

Conscious understanding is a comparatively slow process, but it can cut down considerably the number of alternatives that need to be seriously consideredand thereby greatly increase the effective depth calculation.  

In other words, a flash of insight can cross large distances of "logical depth" a la Charles H. Bennett.  Insight is like a wormhole, a directed wormhole, through solution space.

diffusion through conformational space?

http://link.springer.com/static-content/lookinside/371/art%253A10.1007%252FBF00163809/000.png

Protein evolution as diffusion through conformational space?

Shouldn't it be diffusion through typographical space?

Another thing:  If it is an easy thing to make a protein for any particular effect, why isn't it exceptionally easy to make a protein that really gums up the works?  either ties itself into a useless little knot or turns into something that binds with all sorts of things it shouldn't and kills its organism (slowly or quickly)?

But then again maybe it isn't that easy:

The need to maintain the structural and functional integrity of an evolving protein severely restricts the repertoire of acceptable amino-acid substitutions^{1, 2, 3, 4}. However, it is not known whether these restrictions impose a global limit on how far homologous protein sequences can diverge from each other. Here we explore the limits of protein evolution using sequence divergence data. We formulate a computational approach to study the rate of divergence of distant protein sequences and measure this rate for ancient proteins, those that were present in the last universal common ancestor. We show that ancient proteins are still diverging from each other, indicating an ongoing expansion of the protein sequence universe. The slow rate of this divergence is imposed by the sparseness of functional protein sequences in sequence space and the ruggedness of the protein fitness landscape: ~98 per cent of sites cannot accept an amino-acid substitution at any given moment but a vast majority of all sites may eventually be permitted to evolve when other, compensatory, changes occur. Thus, ~3.5 × 10⁹ yr has not been enough to reach the limit of divergent evolution of proteins, and for most proteins the limit of sequence similarity imposed by common function may not exceed that of random sequences.

2^219 states

2²¹⁹ states

But that's just one star, and a measly one at that. A typical supernova releases something like 10⁵¹ ergs. (About a hundred times as much energy would be released in the form of neutrinos, but let them go for now.) If all of this energy could be channeled into a single orgy of computation, a 219-bit counter could be cycled through all of its states.
    https://www.schneier.com/blog/archives/2009/09/the_doghouse_cr.html

space walk

What I took away from Yockey's book most of all was the idea that mutational walks (the neutral diffusion through phase space) are not walking from residue to residue but from codon to codon.  Yockey said that it was important that the substitutable amino acids form a Hamming chain.  If one of the links in the Hamming chain was not substitutable in the sense of the others in the set of functionally similar amino acids (i.e. the residues that fell within the same sphere in Borstnik-Hofaker space) then the walk was truncated.  It would imply that even a double-mutation can't be expected to happen regularly over evolutionary epochs.

And it calls into question whether evolutionary walks through protein space can go against the grain.  Just how sensitive is the process to loss of function?  For any population, there is some threshold over which the effect of the residue substitution is deleterious enough to not be ignored.  The tendency of the mutation to spread is not only stunted but negatively selected against.  Some "neutral" mutations are only neutral because they are masked by the noise of thousands of other mildly deleterious alleles.  And then there is the thing that is still largely ignored:  Some mutations simply make the protein non-functional; not worse than comparable its neighbors in protein space, but no good at all.

It would be interesting to see what comes of studies in programmable matter with regard to random programming.

Also need to consider in what sense substitutability affects the information in each codon.