Are articles in high-impact journals more like designer handbags, or monarch butterflies?

Monarch butterfly handbag
Monarch butterfly handbag (src)

US biologist Randy Schekman, who shared this year’s physiology and medicine Nobel prize, has made prompt use of his new bully pulpit. In
How journals like Nature, Cell and Science are damaging science: The incentives offered by top journals distort science, just as big bonuses distort banking
he singled out these “luxury” journals as a particularly harmful part of the current milieu in which “the biggest rewards follow the flashiest work, not the best,” and he vowed no longer to publish in them. An accompanying Guardian article includes defensive quotes from representatives of Science and Nature, especially in response to Schekman’s assertions that the journals favor controversial articles over boring but scientifically more important ones like replication studies, and that they deliberately seek to boost their impact factors by restricting the number of articles published, “like fashion designers who create limited-edition handbags or suits.”  Focusing on journals, his main concrete suggestion is to increase the role of open-access online journals like his elife, supported by philanthropic foundations rather than subscriptions. But Schekman acknowledges that blame extends to funding organizations and universities, which use publication in high-impact-factor journals as a flawed proxy for quality, and to scientists who succumb to the perverse incentives to put career advancement ahead of good science.  Similar points were made last year in Serge Haroche’s thoughtful piece on why it’s harder to do good science now than in his youth.   This, and Nature‘s recent story on Brazilian journals’ manipulation of impact factor statistics, illustrate how prestige journals are part of the solution as well as the problem.
Weary of people and institutions competing for the moral high ground in a complex terrain, I sought a less value-laden approach,  in which scientists, universities, and journals would be viewed merely as interacting IGUSes (information gathering and utilizing systems), operating with incomplete information about one another. In such an environment, reliance on proxies is inevitable, and the evolution of false advertising is a phenomenon to be studied rather than disparaged.  A review article on biological mimicry introduced me to some of the refreshingly blunt standard terminology of that field.  Mimicry,  it said,  involves three roles:  a model,  i.e.,  a living or material agent emitting perceptible signals, a mimic that plagiarizes the model, and a dupe whose senses are receptive to the model’s signal and which is thus deceived by the mimic’s similar signals.  As in human affairs, it is not uncommon for a single player to perform several of these roles simultaneously.

Test your intuition

The name of this post was shamelessly stolen from Gil Kalai’s popular series Test Your Intuition. But today’s post will be testing our physics intuition, rather than our mathematical intuition. Although this is a quantum blog, we’ll look at the behavior of a classical fluid.
The question is: what happens when you soak a washcloth with water and then ring it out… in zero gravity?
Think about it for a few minutes before watching the result of the actual experiment below.

Apocalypses, Firewalls, and Boltzmann Brains

Last week’s plebeian scare-mongering about the world ending at the wraparound of the Mayan calendar did not distract sophisticated readers of gr-qc and quant-ph from a more arcane problem, the so-called Firewall Question.  This concerns what happens to Alice when she falls through the event horizon of a large, mature black hole.  Until recently it was thought that nothing special would happen to her other than losing her ability to communicate with the outside world, regardless of whether the black hole was old or young, provided it was large enough for space to be nearly flat at the horizon.  But lately  Almheiri, Marlof, Polchinski, and Sully argued (see also Preskill’s Quantum Frontiers post and especially the comments on it) that she instead would be vaporized instantly and painlessly as she crossed the horizon.  From Alice’s point of view, hitting the firewall would be like dying in her sleep: her experience would simply end.  Alice’s friends wouldn’t notice the firewall either, since they would either be outside the horizon where they couldn’t see her, or inside and also vaporized. So the firewall question, aside from being central to harmonizing no-cloning with black hole complementarity, has a delicious epistemological ambiguity.
Notwithstanding these conceptual attractions, firewalls are not a pressing practical problem, because the universe is far too young to contain any of the kind of black holes expected to have them (large black holes that have evaporated more than half their total mass).
A more worrisome kind of instant destruction, both practically and theoretically, is the possibility that the observable universe—the portion of the universe accessible to us—may be in a metastable state, and might decay catastrophically to a more stable ground state.    Once nucleated, either spontaneously or through some ill-advised human activity,  such a vacuum phase transition would propagate at the speed of light, annihilating the universe we know before we could realize—our universe would die in its sleep.  Most scientists, even cosmologists, don’t worry much about this either, because our universe has been around so long that spontaneous nucleation appears less of a threat than other more localized disasters, such as a nearby supernova or collision with an asteroid.  When some people, following the precautionary principle,  tried to stop a proposed high-energy physics experiment at Brookhaven Lab because it might nucleate a vacuum phase transition or some other world-destroying disaster, prominent scientists argued that if so, naturally occurring cosmic-ray collisions would already have triggered the disaster long ago.  They prevailed, the experiment was done, and nothing bad happened.
The confidence of most scientists, and laypeople, in the stability of the universe rests on gut-level inductive reasoning: the universe contains ample evidence (fossils, the cosmic microwave background, etc.) of having been around for a long time, and it hasn’t disappeared lately.  Even my four year old granddaughter understands this.  When she heard that some people thought the world would end on Dec 21, 2012, she said, “That’s silly.  The world isn’t going to end.”
The observable universe is full of regularities, both obvious and hidden, that underlie the success of science, the human activity which the New York Times rightly called the best idea of the second millennium.  Several months ago in this blog, in an effort to formalize the kind of organized complexity which science studies, I argued that a structure should be considered complex, or logically deep, to the extent that it contains internal evidence of a complicated causal history, one that would take a long time for a universal computer to simulate starting from an algorithmically random input.
Besides making science possible, the observable universe’s regularities give each of us our notion of “us”, of being one of several billion similar beings, instead of the universe’s sole sentient inhabitant.  An extreme form of that lonely alternative, called a Boltzmann brain, is a hypothetical fluctuation arising within a large universe at thermal equilibrium, or in some other highly chaotic state,  the fluctuation being just large enough to support a single momentarily functioning human brain, with illusory perceptions of an orderly outside world, memories of things that never happened, and expectations of a future that would never happen, because the brain would be quickly destroyed by the onslaught of its hostile actual environment.  Most people don’t believe they are Boltzmann brains because in practice science works.   If a Boltzmann brain observer lived long enough to explore some part of its environment not prerequisite to its own existence, it would find chaos there, not order, and yet we generally find order.
Over the last several decades, while minding their own business and applying the scientific method in a routine way, cosmologists stumbled into an uncomfortable situation: the otherwise successful theory of eternal inflation seemed to imply that tiny Boltzmann brain universes were more probable than big, real universes containing galaxies, stars, and people.  More precisely, in these models, the observable universe is part of an infinite seething multiverse, within which real and fake universes each appear infinitely often, with no evident way of defining their relative probabilities—the so-called “measure problem”.
Cosmologists Rafael Bousso and Leonard Susskind and Yasunori Nomura (cf also a later paper) recently proposed a quantum solution to the measure problem, treating the inflationary multiverse as a superposition of terms, one for each universe, including all the real and fake universes that look more or less like ours, and many others whose physics is so different that nothing of interest happens there.  Sean Carroll comments accessibly and with cautious approval on these and related attempts to identify the multiverse of inflation with that of many-worlds quantum mechanics.
Aside from the measure problem and the nature of the multiverse, it seems to me that in order to understand why the observed universe is complicated and orderly, we need to better characterize what a sentient observer is.  For example, can there be a sentient observer who/which is not complex in the sense of logical depth?  A Boltzmann brain would at first appear to be an example of this, because though (briefly) sentient it has by definition not had a long causal history.  It is nevertheless logically deep, because despite its  short actual history it has the same microanatomy as a real brain, which (most plausibly) has had a long causal history.   The Boltzmann brain’s  evidence of having had long history is thus deceptive, like the spurious evidence of meaning the protagonists in Borges’ Library of Babel find by sifting through mountains of chaotic books, until they find one with a few meaningful lines.
I am grateful to John Preskill and especially Alejandro Jenkins for helping me correct and improve early versions of this post, but of course take full responsibility for the errors and misconceptions it may yet contain.

Is science on trial in Italy?

credit: Reuters/Alessandro Bianchi

Big news from Italy today, where a regional court has ruled that six Italian scientists (and one ex-government official) are guilty of multiple manslaughter for the deaths of 309 people that were killed in the L’Aquila earthquake in 2009.
The reaction in the English-speaking press seems largely to showcase the angle that the scientists are being persecuted for failing to accurately predict when the earthquake would hit. They are rightly pointing out that there is no currently accepted scientific method for short-term earthquake prediction, and hence there can be no way to fault the scientists for a failure to make an accurate prediction. As the BBC puts it, “The case has alarmed many in the scientific community, who feel science itself has been put on trial.”
And indeed, reading through the technical report of the “grandi rischi” commission, there does not seem to be anything unreasonable that these scientists say, either before or after the earthquake. (Unfortunately the reports are only in Italian… ma non è troppo difficile perché questo aiuta.) There is no evidence here of either misconduct or manipulation of data.
However, this is a rather delicate issue, and the above arguments in defense of the scientists may be red herrings. As BBC science correspondent Jonathan Amos reports, the issue which was under deliberation at the trial was rather about whether the scientists (under pressure from the Civil Defense) issued public statements that were overly downplaying the risk. In fact, one official, Guido Bertolaso, was recorded in a tapped telephone conversation explicitly calling for such action, and I’m sure that charges will be brought against him as well, if they haven’t already. (Strangely, the wiretap was part of a separate investigation and went unnoticed until January of this year, hence the delay.)
In fact, after the aforementioned conversation with Mr. Bertolaso, one of the seven defendants, Mr. de Bernardinis (the ex-official, not one of the scientists) told a reporter that there was “no danger” posed by the ongoing tremors, and that “the scientific community continues to confirm to me that in fact it is a favorable situation” and that the public should just “relax with a Montepulciano” (a glass of red wine from the region).  Contrast this with the fact that strong earthquakes do tend to correlate time-wise with an increase in smaller tremors. Thus, although the total probability of a large event remains low, it definitely increases when there are more tremors.
Thus, the case is not just another in the long Italian tradition of show-trials persecuting scientists (c.f. Bruno, Galileo). It is at the very least a complex and delicate case, and we should resist the knee-jerk reaction to rush to the defense of our fellow scientists without first getting all of the facts. My personal opinion is that I’m reserving judgement on the guilt or innocence of the scientists until I get more information, though Mr. de Bernardinis is not looking so good.
(Update: as Aram rightly points out in the comments, a manslaughter charge seems very excessive here, and I suppose charges of negligence or maybe wrongful death would seem more appropriate.)
But there is at least one other tragedy here, and that is that these scientists might be essentially the only ones who face a trial. There are many other failure points in the chain of responsibility that led to the tragic deaths. For example, it has come to light that many of the buildings were not built according to earthquake safety regulations; the contractors and government officials were cutting corners in very dangerous ways. If those accusations are true, then that is very serious indeed, and it would be a travesty of justice if the guilty parties were to go unpunished.
Update: Michael Nielsen points to an outstanding article that I missed (from over a month ago!) that discusses exactly these points. Let me quote extensively from the article:

Picuti [one of the prosecutors] made it clear that the scientists are not accused of failing to predict the earthquake. “Even six-year old kids know that earthquakes cannot be predicted,” he said. “The goal of the meeting was very different: the scientists were supposed to evaluate whether the seismic sequence could be considered a precursor event, to assess what damages had already happened at that point, to discuss how to mitigate risks.” Picuti said the panel members did not fulfill these commitments, and that their risk analysis was “flawed, inadequate, negligent and deceptive”, resulting in wrong information being given to citizens.
Picuti also rejected the point – made by the scientists’ lawyers – that De Bernardinis alone should be held responsible for what he told the press. He said that the seismologists failed to give De Bernardinis essential information about earthquake risk. For example, he noted that in 1995 one of the indicted scientists… had published a study that suggetsed a magnitude-5.9 earthquake in the L’Aquila area was considered highly probable within 20 years… [and] estimated the probability of a magnitude 5.5 shock in the following decade to be as high as 15%. Such data were not discussed at the meeting, as the minutes show.
“Had Civil Protection officials known this, they would probably have acted differently,” said Picuti. “They were victims of the seismologists”.

Haroche and Wineland win Physics Nobel

David Wineland
Serge Haroche

The physics prize was shared between experimentalists Serge Haroche and David Wineland, longtime leaders in the study of atom-photon interaction.  In recent decades both have honed their techniques to meet the challenges and opportunities opened by “quantum information science” which aims to rebuild the theory and practice of communication and computation on quantum foundations.  This change of viewpoint was led by theorists, beginning with John Bell, and was initially regarded skeptically not only by information theorists and computer scientists, on whose turf it encroached, but even by many physicists, who saw a lot of theorizing, verging on philosophy, with little practice to back it up.  Haroche, working often with Rydberg atoms and microwave cavities, and Wineland, with trapped ions and optical fields, took the new approach seriously, and over many years have provided much of the solid foundation of practice that has by now has earned the field the right to be taken seriously.  At the same time both researchers have done their part to restrain the inevitable hype.    A decade and a half ago Haroche, in articles like “Quantum Computing: Dream or Nightmare” pointed out how difficult building a quantum computer would be, while always believing it possible in principle, and in the mean time produced, with his group, an impressive stream of experimental results and technical improvements  that made it ever more practical.  In the same vein, Wineland, when asked if ion traps were the right hardware for building a quantum computer, answered that whatever advantage they had was like being 10 feet ahead at the start of a 10 mile race.  Then like Haroche he went ahead making steady progress in the control and measurement of individual particles, with applications quite apart from that distant goal.
Both men are consummate experimentalists, finding and adapting whatever it takes.  I visited Wineland’s lab about a decade ago and noticed a common dishwashing glove (right handed and light blue, as I recall) interposed between the ion trap’s optical window and a CCD camera focused the ions within.   I asked David what its function was among all the more professional looking equipment.   He said this particular brand of gloves happened to be quite opaque with a matte black inside as good as anything he could get from an optics catalog, meanwhile combining moderate flexibility with sufficient rigidity to stay out of the way of the light path, unlike, say, a piece of black velvet.  Indeed the cut-off thumb fitted nicely onto the optical window, and the wrist was snugly belted around the front of the camera, leaving the fingers harmlessly but ludicrously poking out at the side.  The physics Nobel has occasioned a lot of press coverage, much of it quite good in conveying the excitement of quantum information science, while restraining unrealistic expectations.   We especially like Jason Palmer’s story from earlier this year which the BBC resurrected to explain a field which this Nobel has suddenly thrust into the limelight.   We congratulate Haroche and Wineland as deserving and timely winners of this first Nobel given to people who could fairly be described, and would now describe themselves, as quantum information scientists.

Physics World gets high on Tel Aviv catnip

It should be no surprise that loose talk by scientists on tantalizing subjects like backward causality can impair the judgment of science writers working on a short deadline.  A recent paper by Aharonov, Cohen, Grossman and Elitzur at Tel Aviv University,  provocatively titled “Can a Future Choice Affect a Past Measurement’s Outcome?” so intoxicated Philip Ball, writing in Physics World,  that a casual reader of his piece would likely conclude  that  the answer was  “Yes!  But no one quite understands how it works,  and it probably has something to do with free will.”  A more sober reading of the original paper’s substantive content would be

  •  As John Bell showed in 1964, quantum systems’ behavior cannot be explained by local hidden variable models of the usual sort, wherein each particle carries information determining the result of any measurement that might be performed on it.
  • The Two State-Vector Formalism (TSFV) for quantum mechanics,  although equivalent in its predictions to ordinary nonlocal quantum theory, can be viewed as a more complicated kind of local hidden variable model, one that, by depending on a final as well as an initial condition, and being local in space-time rather than space, escapes Bell’s prohibition .

This incident illustrates two unfortunate tendencies in quantum foundations research:

  • Many in the field believe in their own formulation or interpretation of quantum mechanics so fervently that they give short shrift to other formulations, rather than treating them more charitably, as complementary approaches to understanding a simple but hard-to-intuit reality.
  • There is a long history of trying to fit the phenomenology of entanglement into inappropriate everyday language, like Einstein’s “spooky action at a distance”.

Surely the worst mistake of this sort was Herbert’s 1981 “FLASH” proposal to use entanglement for superluminal signaling, whose refutation may have hastened the discovery of the no-cloning theorem.  The Tel Aviv authors would never make such a crude mistake—indeed, far from arguing that superluminal signalling is possible, they use it as a straw man for their formalism to demolish.   But unfortunately, to make their straw man look stronger before demolishing him, they use language that, like Einstein’s,  obscures the crucial difference between communication and correlation.  They say that the initial (weak) measurement outcomes “anticipate the experimenter’s future choice” but that doing so causes no violation of causality because the “anticipation is encrypted”.  This is as wrongheaded as saying that when Alice sends Bob a classical secret key, intending to use it for one-time-pad encryption,  that the key is already an encrypted anticipation of  whatever message she might later send with it.   Or to take a more quantum example, it’s like saying that half of any maximally entangled  pair of qubits is already an encrypted anticipation of whatever quantum state might later be teleported through it.
Near the end of their paper the Tel Aviv group hits another hot button,  coyly suggesting that encrypted anticipation may help explain free will, by giving humans “full freedom from both past and future constraints.”  The issue of free will appeared also in Ball’s piece (following a brief but fair summary of my critique) as a quote attributing to Yakir Aharonov, the senior Tel Aviv author, the opinion that  humans have free will even though God knows exactly what they will do.
The authors, and reviewer, would have served their readers better by eschewing  the “concept” of  encrypted anticipation and instead concentrating on how TSVF makes a local picture of quantum evolution possible.  In particular they could have compared TSVF with another attempt to give orthodox quantum mechanics a fully local explanation,  Deutsch and Hayden’s 1999 information flow formalism.

This post was supported by Goldman-Sachs Grant No. GS98039

After my earlier post about the defense budget, I thought it might be nice if there were some other similar-sized revenue streams that we could tap into other than DoD funding.  It got me thinking… who has the most money? Governments aside (which already have schemes for funding science), it has to be large corporations and big investment banks.
While some large corporations have R & D divisions (e.g. the quantum group at IBM), I’m not aware of any investment bank that has one, despite the large number of physicists, mathematicians and computer scientists that they employ. Could we possibly get a bank to directly fund scientific research? After all, what is the entire NSF budget of $7 billion to a big investment bank? A JP Morgan executive loses that kind of money in the cushions of his couch.
Here is something that could possibly entice one of these entities to invest in physics: using neutrinos to do high-frequency trading. While all those other suckers are busy sending signals overland via satellites and fiber optics, you just take a short cut with a neutrino beam straight through the center of the earth!  My back-of-the-envelope calculation suggests an 18 ms difference to send a signal through the Earth from NYC to Shanghai rather than over the surface. You could make the trade and still have time to enjoy a quick blink afterward.
In fact, a group of physicists at Fermilab have recently done an experiment (arXiv) that demonstrated using a neutrino beam to (classically 🙂 ) communicate through the Earth. The bit rate was low, only .1 bits per second, and the distance was only 240m. I’m sure one of the milestones on their Goldman-Sachs grant is to get that up to 1bps and 1km before the program review.

Rounding Error in the Defense Budget

I recently (and somewhat belatedly) came across the following news item:

NASA gets two military spy telescopes for astronomy

The gist of the article is that the National Reconnaissance Office (NRO) just donated two telescopes with greater optical capabilities than the Hubble space telescope. For free.
Ironically, NASA may not have the budget to actually put the telescopes into space and run them. This is sort of like if someone sees that you’re parched with thirst, and they decide to give you a bottle of wine that they aren’t interested in drinking anymore, because presumably they have much better wine now. But you’re too poor to afford a bottle opener.
The Hubble cost a lot of money to build. The low-end estimate is USD $2.5 billion, but that is probably an underestimate by a factor of 2. That’s a lot of money, but it will barely buy you a week in Iraq, if you’re the US military.
Let’s assume that the cost to build those telescopes was approximately the same as the Hubble. This means that the cost of the two NRO telescopes combined is about the same as the entire $7 billion budget of the NSF for FY2012.
Of course, US science does get money from the Department of Defense. But the “pure” science budget for the entire US is just a rounding error compared to the total DoD budget.

What increases when a self-organizing system organizes itself? Logical depth to the rescue.

(An earlier version of this post appeared in the latest newsletter of the American Physical Society’s special interest group on Quantum Information.)
One of the most grandly pessimistic ideas from the 19th century is that of  “heat death” according to which a closed system, or one coupled to a single heat bath at thermal  equilibrium,  eventually inevitably settles into an uninteresting state devoid of life or macroscopic motion.  Conversely, in an idea dating back to Darwin and Spencer, nonequilibrium boundary conditions are thought to have caused or allowed the biosphere to self-organize over geological time.  Such godless creation, the bright flip side of the godless hell of heat death, nowadays seems to worry creationists more than Darwin’s initially more inflammatory idea that people are descended from apes. They have fought back, using superficially scientific arguments, in their masterful peanut butter video.
Self-organization versus heat death
Much simpler kinds of complexity generation occur in toy models with well-defined dynamics, such as this one-dimensional reversible cellular automaton.  Started from a simple initial condition at the left edge (periodic, but with a symmetry-breaking defect) it generates a deterministic wake-like history of growing size and complexity.  (The automaton obeys a second order transition rule, with a site’s future differing from its past iff exactly two of its first and second neighbors in the current time slice, not counting the site itself, are black and the other two are white.)

Fig 2.

Time →
But just what is it that increases when a self-organizing system organizes itself?
Such organized complexity is not a thermodynamic potential like entropy or free energy.  To see this, consider transitions between a flask of sterile nutrient solution and the bacterial culture it would become if inoculated by a single seed bacterium.  Without the seed bacterium, the transition from sterile nutrient to bacterial culture is allowed by the Second Law, but prohibited by a putative “slow growth law”, which prohibits organized complexity from increasing quickly, except with low probability.
Fig. 3

The same example shows that organized complexity is not an extensive quantity like free energy.  The free energy of a flask of sterile nutrient would be little altered by adding a single seed bacterium, but its organized complexity must have been greatly increased by this small change.  The subsequent growth of many bacteria is accompanied by a macroscopic drop in free energy, but little change in organized complexity.
The relation between universal computer programs and their outputs has long been viewed as a formal analog of the relation between theory and phenomenology in science, with the various programs generating a particular output x being analogous to alternative explanations of the phenomenon x.  This analogy draws its authority from the ability of universal computers to execute all formal deductive processes and their presumed ability to simulate all processes of physical causation.
In algorithmic information theory the Kolmogorov complexity, of a bit string x as defined as the size in bits of its minimal program x*, the smallest (and lexicographically first, in case of ties) program causing a standard universal computer U to produce exactly x as output and then halt.
 x* = min{p: U(p)=x}
Because of the ability of universal machines to simulate one another, a string’s Kolmogorov complexity is machine-independent up to a machine-dependent additive constant, and similarly is equal to within an additive constant to the string’s algorithmic entropy HU(x), the negative log of the probability that U would output exactly x and halt if its program were supplied by coin tossing.    Bit strings whose minimal programs are no smaller than the string itself are called incompressible, or algorithmically random, because they lack internal structure or correlations that would allow them to be specified more concisely than by a verbatim listing. Minimal programs themselves are incompressible to within O(1), since otherwise their minimality would be undercut by a still shorter program.  By contrast to minimal programs, any program p that is significantly compressible is intrinsically implausible as an explanation for its output, because it contains internal redundancy that could be removed by deriving it from the more economical hypothesis p*.  In terms of Occam’s razor, a program that is compressible by s bits deprecated as an explanation of its output because it suffers from  s bits worth of ad-hoc assumptions.
Though closely related[1] to statistical entropy, Kolmogorov complexity itself is not a good measure of organized complexity because it assigns high complexity to typical random strings generated by coin tossing, which intuitively are trivial and unorganized.  Accordingly many authors have considered modified versions of Kolmogorov complexity—also measured in entropic units like bits—hoping thereby to quantify the nontrivial part of a string’s information content, as opposed to its mere randomness.  A recent example is Scott Aaronson’s notion of complextropy, defined roughly as the number of bits in the smallest program for a universal computer to efficiently generate a probability distribution relative to which x  cannot efficiently be recognized as atypical.
However, I believe that entropic measures of complexity are generally unsatisfactory for formalizing the kind of complexity found in intuitively complex objects found in nature or gradually produced from simple initial conditions by simple dynamical processes, and that a better approach is to characterize an object’s complexity by the amount of number-crunching (i.e. computation time, measured in machine cycles, or more generally other dynamic computational resources such as time, memory, and parallelism) required to produce the object from a near-minimal-sized description.
This approach, which I have called  logical depth, is motivated by a common feature of intuitively organized objects found in nature: the internal evidence they contain of a nontrivial causal history.  If one accepts that an object’s minimal program represents its most plausible explanation, then the minimal program’s run time represents the number of steps in its most plausible history.  To make depth stable with respect to small variations in x or U, it is necessary also to consider programs other than the minimal one, appropriately weighted according to their compressibility, resulting in the following two-parameter definition.

  • An object  is called  d-deep with  s  bits significance iff every program for U to compute x in time <d is compressible by at least s bits. This formalizes the idea that every hypothesis for  x  to have originated more quickly than in time  d  contains  s bits worth of ad-hoc assumptions.

Dynamic and static resources, in the form of the parameters  d  and  s,  play complementary roles in this definition:  d  as the quantifier and  s  as the certifier of the object’s nontriviality.  Invoking the two parameters in this way not only stabilizes depth   with respect to small variations of  x and U, but also makes it possible to prove that depth obeys a slow growth law, without which any mathematically definition of organized complexity would seem problematic.

  • A fast deterministic process cannot convert shallow objects to deep ones, and a fast stochastic process can only do so with low probability.  (For details see Bennett88.)

Logical depth addresses many infelicities and problems associated with entropic measures of complexity.

  • It does not impose an arbitrary rate of exchange between the independent variables of strength of evidence and degree of nontriviality of what the evidence points to, nor an arbitrary maximum complexity that an object can have, relative to its size.  Just as a microscopic fossil can validate an arbitrarily long evolutionary process, so a small fragment of a large system, one that has evolved over a long time to a deep state, can contain evidence of entire depth of the large system, which may be more than exponential in the size of the fragment.
  • It helps explain the increase of complexity at early times and its decrease at late times by providing different mechanisms for these processes.  In figure 2, for example, depth increases steadily at first because it reflects the duration of the system’s actual history so far.  At late times, when the cellular automaton has run for a generic time comparable to its Poincare recurrence time, the state becomes shallow again, not because the actual history was uneventful, but because evidence of that history has become degraded to the point of statistical insignificance, allowing the final state to be generated quickly from a near-incompressible program that short-circuits the system’s actual history.
  • It helps explain while some systems, despite being far from thermal equilibrium, never self-organize.  For example in figure 1, the gaseous sun, unlike the solid earth, appears to lack means of remembering many details about its distant past.  Thus while it contains evidence of its age (e.g. in its hydrogen/helium ratio) almost all evidence of particular details of its past, e.g. the locations of sunspots, are probably obliterated fairly quickly by the sun’s hot, turbulent dynamics.  On the other hand, systems with less disruptive dynamics, like our earth, could continue increasing in depth for as long as their nonequilibrium boundary conditions persisted, up to an exponential maximum imposed by Poincare recurrence.
  • Finally, depth is robust with respect to transformations that greatly alter an object’s size and Kolmogorov complexity, and many other entropic quantities, provided the transformation leaves intact significant evidence of a nontrivial history. Even a small sample of the biosphere, such as a single DNA molecule, contains such evidence.  Mathematically speaking, the depth of a string x is not much altered by replicating it (like the bacteria in the flask), padding it with zeros or random digits, or passing it though a noisy channel (although the latter treatment decreases the significance parameter s).  If the whole history of the earth were derandomized, by substituting deterministic pseudorandom choices for all its stochastic accidents, the complex objects in this substitute world would have very little Kolmogorov complexity, yet their depth would be about the same as if they had resulted from a stochastic evolution.

The remaining infelicities of logical depth as a complexity measure are those afflicting computational complexity and algorithmic entropy theories generally.

  • Lack of tight lower bounds: because of open P=PSPACE question one cannot exhibit a system that provably generates depth more than polynomial in the space used.
  • Semicomputability:  deep objects can be proved deep (with exponential effort) but shallow ones can’t be proved shallow.  The semicomputability of depth, like that of Kolmogorov complexity, is an unavoidable consequence of the unsolvability of the halting problem.

The following observations can be made partially mitigating these infelicities.

  • Using the theory of cryptographically strong pseudorandom functions one can argue (if such functions exist) that deep objects can be produced efficiently, in time polynomial and space polylogarithmic in their depth, and indeed that they are produced efficiently by some physical processes.
  • Semicomputability does not render a complexity measure entirely useless. Even though a particular string cannot be proved shallow, and requires an exponential amount of effort to prove it deep, the depth-producing properties of stochastic processes can be established, assuming the existence of cryptographically strong pseudorandom functions. This parallels the fact that while no particular string can be proved to be algorithmically random (incompressible), it can be proved that the statistically random process of coin tossing produces algorithmically random strings with high probability.

Granting that a logically deep object is one plausibly requiring a lot of computation to produce, one can consider various related notions:

  • An object  y  is deep relative to  x  if all near-minimal sized programs for computing  y  from  x  are slow-running.  Two shallow objects may be deep relative to one another, for example a random string and its XOR with a deep string.
  • An object can be called cryptic if it is computationally difficult to obtain a near- minimal sized program for the object from the object itself, in other words if any near-minimal sized program for x is deep relative to x.  One-way functions, if they exist, can be used to define cryptic objects; for example, in a computationally secure but information theoretically insecure cryptosystem, plaintexts should be cryptic relative to their ciphertexts.
  • An object can be called ambitious if, when presented to a universal computer as input, it causes the computer to embark on a long but terminating computation. Such objects, though they determine a long computation, do not contain evidence of it actually having been done.  Indeed they may be shallow and even algorithmically random.
  • An object can be called wise if it is deep and a large and interesting family of other deep objects are shallow relative to it. Efficient oracles for hard problems, such as the characteristic function of an NP-complete set, or the characteristic set K of the halting problem, are examples of wise objects.  Interestingly, Chaitin’s omega is an exponentially more compact oracle for the halting problem than K is, but it is so inefficient to use that it is shallow and indeed algorithmically random.

Further details about these notions can be found in Bennett88.  K.W. Regan in Dick Lipton’s blog discusses the logical depth of Bill Gasarch’s recently discovered solutions to the 17-17 and 18×18 four-coloring problem
I close with some comments on the relation between organized complexity and thermal disequilibrium, which since the 19th century has been viewed as an important, perhaps essential, prerequisite for self-organization.   Broadly speaking, locally interacting systems at thermal equilibrium obey the Gibbs phase rule, and its generalization in which the set of independent parameters is enlarged to include not only intensive variables like temperature, pressure and magnetic field, but also all parameters of the system’s Hamiltonian, such as local coupling constants.   A consequence of the Gibbs phase rule is that for generic values of the independent parameters, i.e. at a generic point in the system’s phase diagram, only one phase is thermodynamically stable.  This means that if a system’s independent parameters are set to generic values, and the system is allowed to come to equilibrium, its structure will be that of this unique stable Gibbs phase, with spatially uniform properties and typically short-range correlations.   Thus for generic parameter values, when a system is allowed to relax to thermal equilibrium, it entirely forgets its initial condition and history and exists in a state whose structure can be adequately approximated by stochastically sampling the distribution of microstates characteristic of that stable Gibbs phase.  Dissipative systems—those whose dynamics is not microscopically reversible or whose boundary conditions prevent them from ever attaining thermal equilibrium—are exempt from the Gibbs phase rule for reasons discussed in BG85, and so are capable, other conditions being favorable, of producing structures of unbounded depth and complexity in the long time limit. For further discussion and a comparison of logical depth with other proposed measures of organized complexity, see B90.

[1] An elementary result of algorithmic information theory is that for any probability ensemble of bit strings (representing e.g. physical microstates), the ensemble’s Shannon entropy differs from the expectation of its members’ algorithmic entropy by at most of the number of bits required to describe a good approximation to the ensemble.


Unindicted co-conspirators — a way around Nobel's 3-person limit?

This is the time of year the selection process begins for next fall’s Nobel Prizes.  Unlike Literature and Peace, most fields of science have become increasingly collaborative over the last century, often forcing Nobel Committees to unduly truncate the list of recipients or neglect major discoveries involving more than three discoverers, the maximum Nobel’s will allows.  A possible escape from this predicament  would  be to choose three official  laureates randomly from a larger set of names, then publish the entire set, along with the fact that the official winners had been chosen randomly from it.   The money of course would go to the three official winners, but public awareness that they were no more worthy than the others might induce them to share it.  A further refinement would be to use weighted probabilities, allowing credit to be allocated unequally, with a similar incentive for the winners to share money and credit according to the published weights, not the actual results, of the selection process.
If the Nobel Foundation’s lawyers could successfully argue that such randomization was consistent with Nobel’s will, the Prizes would better reflect the collaborative nature of modern science, at the same time lessening unproductive competition among  scientists to make it into the top three.